A ranking model for the greedy algorithm and discrete convexity (Q2429474)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A ranking model for the greedy algorithm and discrete convexity |
scientific article |
Statements
A ranking model for the greedy algorithm and discrete convexity (English)
0 references
27 April 2012
0 references
Matroid-type Greedy algorithms are analyzed and generalized in this paper. The authors introduce a combinatorial model, which associates with the Greedy algorithm a certain functional. It is proved that the named functional is concave if and only if the Greedy algorithm produces optimal solutions.
0 references
greedy algorithm
0 references
linear program
0 references
matroid
0 references
