Submodular linear programs on forests

DOI10.1007/BF02592089MaRDI QIDQ1919093zbMATH OpenFDO

Authors U. Faigle, Walter Kern

Publication date 23 February 1997

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

Full work available at URL https://doi.org/10.1007/BF02592089

zbMATH Keywords

distributive latticeEdmonds' greedy algorithm for matroidsMonge propertyNW-corner rule for transportation problemsoptimal greedy algorithms for rooted forestsordered setsubmodular function

Mathematics Subject Classification ID

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

Recommendations

• A general class of greedily solvable linear programs
• scientific article; zbMATH DE number 1263283
• On the core of ordered submodular cost games
• scientific article; zbMATH DE number 3970528

Cites work

• A Monge property for the \(d\)-dimensional transportation problem
• Generalized polymatroids and submodular flows
• scientific article; zbMATH DE number 4027489 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 1263283 (Why is no real title available?)
• scientific article; zbMATH DE number 3272833 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Monge sequences and a simple assignment algorithm
• Perspectives of Monge properties in optimization

Cited in

(14)

• 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
• A greedy algorithm for convex geometries
• On the core of ordered submodular cost games
• K-submodular functions and convexity of their Lovász extension
• Perspectives of Monge properties in optimization
• Lattice polyhedra and submodular flows
• Structural aspects of ordered polymatroids
• Dual greedy polyhedra, choice functions, and abstract convex geometries
• A general class of greedily solvable linear programs
• scientific article; zbMATH DE number 1263283 (Why is no real title available?)
• A Hierarchical Model for Cooperative Games
• Note on pseudolattices, lattices and submodular linear programs

This page was built for publication: Submodular linear programs on forests

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