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

• Autorzy: Haider S. A.

Identyfikatory

DOI

10.17951/AI.2016.16.2.48

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

contraction; greedy; independence Matroid; maximal

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2016
• Tom: Vol. 16, no. 2
• Strony: 48--50
• Opis fizyczny: Bibliogr. 4 poz.,

Twórcy

autor

Haider S. A.

• Zakir Husain College of Eng. & Tech., Aligarh Muslim University, Aligarh, Uttar Pradesh, India

Bibliografia

• [1] “Introduction to Algorithms. Third Edition.” Cormen,Leiserson,Rivest and Stein.
• [2] 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.
• [3] B. Korte and L. Lovasz, “Structural properties of greedoids.”, Combinatorica, 3(3–4):359–374, 1983
• [4] 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.