8 papers · 1 filter
Lifts for Voronoi cells of lattices
Matthias Schymura, Ina Seidel, Stefan Weltge
Many polytopes arising in polyhedral combinatorics are linear projections of higher-dimensional polytopes with significantly fewer facets. Such lifts may yield compressed represent…
Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
Michele Conforti, Samuel Fiorini, Tony Huynh +1
Let be an -node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC'17) for bimodular integer programs can be used to find a maxi…
Minimum-cost integer circulations in given homology classes
Sarah Morell, Ina Seidel, Stefan Weltge
Let be a directed graph cellularly embedded in a surface together with non-negative cost on its arcs. Given any integer circulation in , we study the problem of finding a mi…
Persistency of Linear Programming Relaxations for the Stable Set Problem
Elisabeth Rodríguez-Heck, Karl Stickler, Matthias Walter +1
The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: f…
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Michele Conforti, Samuel Fiorin, Tony Huynh +2
Consider the family of graphs without node-disjoint odd cycles, where is a constant. Determining the complexity of the stable set problem for such graphs is a lon…
Extended Formulations for Radial Cones
Matthias Walter, Stefan Weltge
This paper studies extended formulations for radial cones at vertices of polyhedra, where the radial cone of a polyhedron at a vertex is the polyhedron defined by…