Submodular linear programs on forests

DOI10.1007/BF02592089zbMath0856.90071MaRDI QIDQ1919093

Ulrich Faigle, Walter Kern

Publication date: 23 February 1997

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

zbMATH Keywords

submodular functionordered setdistributive latticeMonge propertyEdmonds' greedy algorithm for matroidsNW-corner rule for transportation problemsoptimal greedy algorithms for rooted forests

Mathematics Subject Classification ID

Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items

K-submodular functions and convexity of their Lovász extension, Dual greedy polyhedra, choice functions, and abstract convex geometries, Perspectives of Monge properties in optimization, Lattice polyhedra and submodular flows, A greedy algorithm for convex geometries, Structural aspects of ordered polymatroids, Note on pseudolattices, lattices and submodular linear programs, A Hierarchical Model for Cooperative Games, A general model for matroids and the greedy algorithm, Base polytopes of series-parallel posets: Linear description and optimization, Some recent results in the analysis of greedy algorithms for assignment problems

Cites Work

• Monge sequences and a simple assignment algorithm
• Generalized polymatroids and submodular flows
• A Monge property for the \(d\)-dimensional transportation problem
• Perspectives of Monge properties in optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item