A ranking model for the greedy algorithm and discrete convexity

U. Faigle, Walter Kern, Britta Peis

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
91 Downloads (Pure)

Abstract

Generalizing the idea of the Lovász extension of a set function and the discrete Choquet integral, we introduce a combinatorial model that allows us to define and analyze matroid-type greedy algorithms. The model is based on a real-valued function v on a (finite) family of sets which yields the constraints of a combinatorial linear program. Moreover, v gives rise to a ranking and selection procedure for the elements of the ground set N and thus implies a greedy algorithm for the linear program. It is proved that the greedy algorithm is guaranteed to produce primal and dual optimal solutions if and only if an associated functional on $\mathbb{R}^N$ is concave. Previous matroid-type greedy models are shown to fit into the present general context. In particular, a general model for combinatorial optimization under supermodular constraints is presented which guarantees the greedy algorithm to work.
Original languageUndefined
Pages (from-to)393-407
Number of pages15
JournalMathematical programming
Volume132
Issue number1-2
DOIs
Publication statusPublished - 2012

Keywords

  • EWI-21699
  • MSC-90C27
  • METIS-289635
  • IR-79977
  • MSC-90C57

Cite this