A ranking model for the greedy algorithm and discrete convexity

Share/Save/Bookmark

Faigle, Ulrich and Kern, Walter and Peis, Britta (2012) A ranking model for the greedy algorithm and discrete convexity. Mathematical programming, 132 (1-2). pp. 393-407. ISSN 0025-5610

open access
[img]
Preview
PDF
207kB
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.
Item Type:Article
Additional information:Open Access
Copyright:© 2012 The Author(s)
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/79977
Official URL:http://dx.doi.org/10.1007/s10107-010-0406-2
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 289635