A ranking model for the greedy algorithm and discrete convexity

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

Preview

PDF
202Kb

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
Copyright:	© 2012 The Author(s)
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 289635