44 citations · 80 across the 32 of their papers we have counts for
4 papers · 1 filter
Uncapacitated Flow-based Extended Formulations
Samuel Fiorini, Kanstantsin Pashkovich
An extended formulation of a polytope is a linear description of this polytope using extra variables besides the variables in which the polytope is defined. The interest of extende…
Stable Sets and Graphs with no Even Holes
Michele Conforti, Bert Gerards, Kanstantsin Pashkovich
We develop decomposition/composition tools for efficiently solving maximum weight stable sets problems as well as for describing them as polynomially sized linear programs (using "…
The Projected Faces Property and Polyhedral Relations
Michele Conforti, Kanstantsin Pashkovich
Margot (1994) in his doctoral dissertation studied extended formulations of combinatorial polytopes that arise from "smaller" polytopes via some composition rule. He introduced the…
Which Nonnegative Matrices Are Slack Matrices?
João Gouveia, Roland Grappe, Volker Kaibel +3
In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack ma…