Publication
McMullen's conditions and some lower bounds for general convex polytopes
Publications associées (19)
On the Volume of the John-Lowner Ellipsoid
We find an optimal upper bound on the volume of the John ellipsoid of a k-dimensional section of the n-dimensional cube, and an optimal lower bound on the volume of the Lowner ellipsoid of a projection of the n-dimensional cross-polytope onto a k-dimension ...
SPRINGER2020Complexity of linear relaxations in integer programming
For a set X of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with X is called the relaxation complexity rc(X). This parameter was introduced by Kaibel & Weltge (2015) and captures the ...
2020Extended Formulations from Communication Protocols in Output-Efficient Time
Yuri Faenza, Manuel Francesco Aprile
Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the exten ...
SPRINGER INTERNATIONAL PUBLISHING AG2019Extension complexity of stable set polytopes of bipartite graphs
Yuri Faenza, Manuel Francesco Aprile
The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...
Springer2017On The Convergence Of The Affine Hull Of The Chvatal-Gomory Closures
Given an integral polyhedron P subset of R-n and a rational polyhedron Q subset of R-n containing the same integer points as P, we investigate how many iterations of the Chvatal-Gomory closure operator have to be performed on Q to obtain a polyhedron conta ...
Siam Publications2013On Polygons Excluding Point Sets
Radoslav Fulek, Balázs Keszegh, Filip Moric
By a polygonization of a finite point set S in the plane we understand a simple polygon having S as the set of its vertices. Let B and R be sets of blue and red points, respectively, in the plane such that is in general position, and the convex hull of B c ...
Springer Japan2013Lifting simplicial complexes to the boundary of convex polytopes
Abstract: A simplicial complex C on a d-dimensional configuration of n points is k-regular if its faces are projected from the boundary complex of a polytope with dimension at most d+k. Since C is obviously (n-d-1)-regular, the set of all integers k for wh ...
Elsevier2012The Holt-Klee condition for oriented matroids
Holt and Klee have recently shown that every (generic) LP orientation of the graph of a d-polytope satisfies a directed version of the d-connectivity property, i.e. there are d internally disjoint directed paths from a unique source to a unique sink. We in ...
2009f-vectors of Minkowski additions of convex polytopes
The objective of this paper is to present two types of results on Minkowski sums of convex polytopes. The first is about a special class of polytopes we call perfectly centered and the combinatorial properties of the Minkowski sum with their own dual. In p ...
20070/1 vertex and facet enumeration with BDDs
In polyhedral studies of 0/1 polytopes two prominent problems exist. One is the vertex enumeration problem: Given a system of inequalities, enumerate its feasible 0/1 points. Another one is the convex hull problem: Given a set of 0/1 points in dimension d, ...
2007