PL EN


Preferences help
enabled [disable] Abstract
Number of results
2016 | 16 | 2 |
Article title

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

Content
Title variants
Languages of publication
EN
Abstracts
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.
Year
Volume
16
Issue
2
Physical description
Dates
published
2016
online
22 - 12 - 2017
Contributors
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.
Document Type
Publication order reference
Identifiers
YADDA identifier
bwmeta1.element.ojs-doi-10_17951_ai_2016_16_2_48
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.