Matroids And Greedy Algorithms. A Deeper Justification of Using Greedy Approach To Find A Maximal set of a Matroid

Syed Aqib Haider

Abstract


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.


Keywords


Contraction, Greedy , Independence Matroid, Maximal

Full Text:

PDF

References


“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.




DOI: http://dx.doi.org/10.17951/ai.2016.16.2.48
Data publikacji: 2017-12-22 09:38:09
Data złożenia artykułu: 2017-12-22 09:37:33

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 Syed Aqib Haider

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.