A ranking model for the greedy algorithm and discrete convexity (Q2429474): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s10107-010-0406-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2102656029 / rank | |||
Normal rank |
Revision as of 01:00, 20 March 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