Uncapacitated flow-based extended formulations
From MaRDI portal
Publication:745688
DOI10.1007/s10107-015-0862-9zbMath1356.90122arXiv1306.3119OpenAlexW1965276692MaRDI QIDQ745688
Samuel Fiorini, Kanstantsin Pashkovich
Publication date: 14 October 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1306.3119
linear programmingcombinatorial optimizationspecial polytopesprogramming involving graphs and networks
Programming involving graphs or networks (90C35) Linear programming (90C05) Combinatorial optimization (90C27)
Related Items (2)
Extended formulations for order polytopes through network flows ⋮ Extension complexity of formal languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Common information and unique disjointness
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- Polyhedral proof methods in combinatorial optimization
- Using separation algorithms to generate mixed integer model reformulations
- Expressing combinatorial optimization problems by linear programs
- Combinatorial bounds on nonnegative rank and extended formulations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- An Algebraic Approach to Symmetric Extended Formulations
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Symmetry Matters for the Sizes of Extended Formulations
- Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic Programming and MaxCutGain
- Optimal Sherali-Adams Gaps from Pairwise Independence
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Lectures on Polytopes
- Integrality gaps for Sherali-Adams relaxations
- Linear vs. semidefinite extended formulations
- An information complexity approach to extended formulations
- Maximum matching and a polyhedron with 0,1-vertices
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Extended formulations in combinatorial optimization
This page was built for publication: Uncapacitated flow-based extended formulations