Article ID Journal Published Year Pages File Type
1142098 Operations Research Letters 2015 4 Pages PDF
Abstract

We show that there exists a family PP of Knapsack polytopes such that for each P∈PP∈P and each ε>0ε>0, any εε-approximated formulation of PP in the original space RnRn requires a number of inequalities that is super-polynomial in nn. This answers a question by Bienstock and McClosky (2012). We also prove that, for any down-monotone polytope, an εε-approximated formulation in the original space can be obtained with inequalities using at most O(1εmin{log(n/ε),n}) different coefficients.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,