Matroids And Greedy Algorithms. A Deeper Justification of Using Greedy Approach To Find A Maximal set of a Matroid
Languages of publication
Greedy algorithms are used in solving a diverse set of problems in small computation time. However, for solving problems using greedy approach, it must be proved that the greedy strategy applies. The greedy approach relies on selection of optimal choice at a local level reducing the problem to a single sub problem, which actually leads to a globally optimal solution. Finding a maximal set from the independent set of a matroid M(S, I) also uses greedy approach and justification is also provided in standard literature (e.g. Introduction to Algorithms by Cormen et .al.). However, the justification does not clearly explain the equivalence of using greedy algorithm and contraction of M by the selected element. This paper thus attempts to give a lucid explanation of the fact that the greedy algorithm is equivalent to reducing the Matroid into its contraction by selected element. This approach also provides motivation for research on the selection of the test used in algorithm which might lead to smaller computation time of the algorithm.
22 - 12 - 2017
- “Introduction to Algorithms. Third Edition.” Cormen,Leiserson,Rivest and Stein.
- B. Korte and L. Lovasz, “Mathematical structures underlying greedy algorithms”. in F. Gecseg, editor, Fundamentals of Computation Theory,volume 117 of Lecture Notes in Computer Science, pages 205–209. Springer, 1981.
- B. Korte and L. Lovasz, “Structural properties of greedoids.”, Combinatorica, 3(3–4):359–374, 1983
- B. Korte and L. Lovasz, “Greedoids - A structural framework for the greedy algorithm.”. In W. Pulleybank, editor, Progress in Combinatorial Optimization, pages 221– 243. Academic Press, 1984.
Publication order reference