0/1 Polytopes with quadratic Chvátal rank

Thomas Rothvoß, Laura Sanitá

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

15 Citaten (Scopus)


For a polytope P, the Chvátal closure P′ ⊆ P is obtained by simultaneously strengthening all feasible inequalities cx ≤ β (with integral c) to cz ≤ ⌊β⌋. The number of iterations of this procedure that are needed until the integral hull of P is reached is called the Chvátal rank. If P ⊆ [0,1]n , then it is known that O(n2 log n) iterations always suffice (Eisenbrand and Schulz (1999)) and at least (1 + 1/e - o(1))n iterations are sometimes needed (Pokutta and Stauffer (2011)), leaving a huge gap between lower and upper bounds. We prove that there is a polytope contained in the 0/1 cube that has Chvátal rank Ω(n2), closing the gap up to a logarithmic factor. In fact, even a superlinear lower bound was mentioned as an open problem by several authors. Our choice of P is the convex hull of a semi-random Knapsack polytope and a single fractional vertex. The main technical ingredient is linking the Chvátal rank to simultaneous Diophantine approximations w.r.t. the ∥ · ∥1-norm of the normal vector defining P.

Originele taal-2Engels
TitelInteger Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Proceedings
Aantal pagina's13
StatusGepubliceerd - 2013
Extern gepubliceerdJa
Evenement16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013 - Valparaiso, Chili
Duur: 18 mrt. 201320 mrt. 2013

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7801 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349


Congres16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013


Duik in de onderzoeksthema's van '0/1 Polytopes with quadratic Chvátal rank'. Samen vormen ze een unieke vingerafdruk.

Citeer dit