Publication

McMullen's conditions and some lower bounds for general convex polytopes

Publications associées (19)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

On the Volume of the John-Lowner Ellipsoid

Grigory Ivanov

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 ...

SPRINGER2020

Complexity of linear relaxations in integer programming

Matthias Schymura

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 ...

2020

Extended 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 AG2019

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. ...

Springer2017

On The Convergence Of The Affine Hull Of The Chvatal-Gomory Closures

Yuri Faenza, Marco Di Summa

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 Publications2013

On 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 Japan2013

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 ...

Elsevier2012

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 ...

2009

f-vectors of Minkowski additions of convex polytopes

Christophe Weibel

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 ...

2007

0/1 vertex and facet enumeration with BDDs

Friedrich Eisenbrand

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