A ranking model for the greedy algorithm and discrete convexity (Q2429474)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6028713
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A ranking model for the greedy algorithm and discrete convexity |
scientific article; zbMATH DE number 6028713 |
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
0.8280202150344849
0 references
0.8280200958251953
0 references
0.8154852986335754
0 references
0.8149539232254028
0 references
