On a General Framework for Network Representability in Discrete Optimization

DOI10.1007/978-3-319-45587-7_32zbMath1452.90222OpenAlexW2509104009MaRDI QIDQ2835692

Yuni Iwamasa

Publication date: 30 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-45587-7_32

zbMATH Keywords

expressive powervalued constraint satisfaction problem\(k\)-submodular functionnetwork representability

Mathematics Subject Classification ID

Integer programming (90C10) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

A compact representation for minimizers of \(k\)-submodular functions ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications

Cites Work

• The expressive power of binary submodular functions
• Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions
• Geometric algorithms and combinatorial optimization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Submodular functions and optimization.
• Half-integrality, LP-branching, and FPT Algorithms
• Towards Minimizing k-Submodular Functions
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• The Complexity of Valued Constraint Satisfaction Problems
• The Power of Linear Programming for General-Valued CSPs
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• Learning with Submodular Functions: A Convex Optimization Perspective
• An Algebraic Theory of Complexity for Discrete Optimization
• Max flows in O(nm) time, or better