A ranking model for the greedy algorithm and discrete convexity (Q2429474): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q170461 |
Changed an Item |
||
| Property / author | |||
| Property / author: Walter Kern / rank | |||
Normal rank | |||
Revision as of 10:17, 10 February 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
