Representation of the greedy algorithms applicability for solving the combinatorial optimization problems based on the hypergraph mathematical structure

Abstract:

This paper deals with representing the structural organization of the combinatorial optimization problems in terms of the hypergraphs, whose hyperedges reflect the solutions of the original problem and its nested subproblems. By using the achievements of the matroid theory, the paper analyzes the parameters of such hypergraphs that determine the suitability of the corresponding problems for being processed by the greedy algorithms. In addition, the study contains the examples of the hypergraph structures constructed for the instance of the minimum spanning tree problem.