A ranking model for the greedy algorithm and discrete convexity (Q2429474): Difference between revisions
From MaRDI portal
Latest revision as of 03:42, 5 July 2024
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
