44 citations · 80 across the 32 of their papers we have counts for
13 papers · 1 filter
Bounds on the number of 2-level polytopes, cones and configurations
Samuel Fiorini, Marco Macchia, Kanstantsin Pashkovich
We prove an upper bound of the form on the number of affine (resp. linear) equivalence classes of, by increasing order of generality, 2-level d-pol…
Enumeration of -level polytopes
Adam Bohn, Yuri Faenza, Samuel Fiorini +3
A (convex) polytope is said to be -level if for every direction of hyperplanes which is facet-defining for , the vertices of can be covered with two hyperplanes of th…
An Elementary Integrality Proof of Rothblum's Stable Matching Formulation
Jochen Könemann, Kanstantsin Pashkovich, Justin Toth
In this paper we provide a short new proof for the integrality of Rothblum's linear description of the convex hull of incidence vectors of stable matchings in bipartite graphs. In…
Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-genus Graphs
Samuel Fiorini, Tony Huynh, Gwenaël Joret +1
We give an -size extended formulation for the spanning tree polytope of an -vertex graph embedded on a surface of genus , improving on t…
Four Dimensional Polytopes of Minimum Positive Semidefinite Rank
João Gouveia, Kanstanstin Pashkovich, Richard Z. Robinson +1
The positive semidefinite (psd) rank of a polytope is the size of the smallest psd cone that admits an affine slice that projects linearly onto the polytope. The psd rank of a d-po…
Cut dominants and forbidden minors
Michele Conforti, Samuel Fiorini, Kanstantsin Pashkovich
The cut dominant of a graph is the unbounded polyhedron whose points are all those that dominate some convex combination of proper cuts. Minimizing a nonnegative linear function ov…
Hidden Vertices in Extensions of Polytopes
Kanstantsin Pashkovich, Stefan Weltge
Some widely known compact extended formulations have the property that each vertex of the corresponding extension polytope is projected onto a vertex of the target polytope. In thi…
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…
Combinatorial Bounds on Nonnegative Rank and Extended Formulations
Samuel Fiorini, Volker Kaibel, Kanstantsin Pashkovich +1
An extended formulation of a polytope P is a polytope Q which can be projected onto P. Extended formulations of small size (i.e., number of facets) are of interest, as they allow t…
Constructing Extended Formulations from Reflection Relations
Volker Kaibel, Kanstantsin Pashkovich
There are many examples of optimization problems whose associated polyhedra can be described much nicer, and with way less inequalities, by projections of higher dimensional polyhe…
Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results
Kanstantsin Pashkovich
It is well known that the permutahedron Pi_n has 2^n-2 facets. The Birkhoff polytope provides a symmetric extended formulation of Pi_n of size Theta(n^2). Recently, Goemans describ…
Symmetry Matters for Sizes of Extended Formulations
Volker Kaibel, Kanstantsin Pashkovich, Dirk Oliver Theis
In 1991, Yannakakis (J. Comput. System Sci., 1991) proved that no symmetric extended formulation for the matching polytope of the complete graph K_n with n nodes has a number of va…