Submodular containment is hard, even for networks

DOI10.1016/0167-6377(96)00016-8zbMath0865.90138OpenAlexW2033520927MaRDI QIDQ2564307

S. Thomas McCormick

Publication date: 14 July 1997

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(96)00016-8

zbMATH Keywords

complexitydynamic gamesnetworkssubmodularitystrongly co-NP-completesubmodular base polyhedra

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Abstract computational complexity for mathematical programming problems (90C60) Games involving graphs (91A43)

Related Items (3)

Robust control of uncertain multi-inventory systems via linear matrix inequality ⋮ Finite alphabet control of logistic networks with discrete uncertainty ⋮ A framework of discrete DC programming by discrete convex analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Submodular functions and optimization
• Geometric algorithms and combinatorial optimization
• Linear programming approach to the control of discrete-time periodic systems with uncertain inputs
• Minimum cuts, modular functions, and matroid polyhedra

This page was built for publication: Submodular containment is hard, even for networks