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 (12). pp. 393407. ISSN 00255610

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 matroidtype greedy algorithms. The model is based on a realvalued 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 is concave. Previous matroidtype 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:  https://doi.org/10.1007/s1010701004062 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 289635