Uncapacitated flow-based extended formulations

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

zbMATH Keywords

linear programmingcombinatorial optimizationspecial polytopesprogramming involving graphs and networks

Mathematics Subject Classification ID

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