A ranking model for the greedy algorithm and discrete convexity

DOI10.1007/S10107-010-0406-2MaRDI QIDQ2429474zbMATH OpenOpenAlexFDO

Authors U. Faigle, Britta Peis, Walter Kern

Publication date 27 April 2012

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s10107-010-0406-2

zbMATH Keywords

greedy algorithmlinear programmatroid

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)

Review text

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.

Recommendations

• A framework for the greedy algorithm
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• A greedy algorithm for some classes of integer programs.
• A generalization of the notion of the rank function of a matroid
• A greedy algorithm for solving a class of convex programming problems and its connection with polymatroid theory

Cites work

• A general model for matroids and the greedy algorithm
• An O (n log n) algorithm for maximum st-flow in a directed planar graph
• Choice functions over a finite set: A summary
• Convex Analysis
• Cores of convex games
• Discrete Convex Analysis
• Dual greedy polyhedra, choice functions, and abstract convex geometries
• scientific article; zbMATH DE number 5764848 (Why is no real title available?)
• scientific article; zbMATH DE number 3970528 (Why is no real title available?)
• scientific article; zbMATH DE number 3634269 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Increasing the rooted connectivity of a digraph by one
• Maximal Flow Through a Network
• Monge extensions of cooperation and communication structures
• On the core of ordered submodular cost games
• Optimum branchings
• Packing rooted directed cuts in a weighted directed graph
• Submodular functions and optimization.
• The theory of convex geometries
• Theory of capacities
• Totally-Balanced and Greedy Matrices

Cited in

(9)

• A general model for matroids and the greedy algorithm
• Greedy oriented flows
• In memoriam Walter Kern
• A generalization of the notion of the rank function of a matroid
• A new ranking model constructing an algorithm based on direct optimization of NDCG
• On the rank functions of \(\mathcal{H}\)-matroids
• A New Look At A Greedy Algorithm For Solving A Class Of Convex Programming Problems
• An order-theoretic framework for the greedy algorithm with applications to the core and Weber set of cooperative games
• The greedy algorithm as a combinatorial principle

This page was built for publication: A ranking model for the greedy algorithm and discrete convexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429474)