A ranking model for the greedy algorithm and discrete convexity

DOI10.1007/s10107-010-0406-2zbMath1250.90073MaRDI QIDQ2429474

Britta Peis, Ulrich Faigle, Walter Kern

Publication date: 27 April 2012

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

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

zbMATH Keywords

greedy algorithm; matroid; linear program

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

Greedy oriented flows

Cites Work

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