On the inapproximability of polynomial-programming, the geometry of stable sets and the power of relaxation

The present paper introduces the geometric rank as a measure for the quality of relaxations of certain combinatorial optimization problems in the realm of polyhedral combinatorics. In particular, this notion establishes a tight relation between the maximum stable set problem from combinatorial optimization, polynomial programming from integer non linear programming and norm maximization, a basic problem from convex maximization and computational convexity. As a consequence we obtain very tight inapproximability bounds even for the largely restricted classes of polynomial programming where the polynomial is just a sum of univariate monomials of degree at most log n, and it is guaranteed that the maximum is attained at a 0-1-vector. More specifically, unless NP = ZPP this problem does not admit a polynomial-time n1 -approximation for any > 0, and does not even admit a polynomial-time n1−O(1/√log log n) - approximation, unless NP = ZPTIME(2O(log n(log log n)3/2)). Similar results are also given for norm maximization. In addition we relate the geometric rank of a relaxation of the stable set polytope to the question whether the separation problem for the relaxation can be solved in polynomial time. Again, the results are nearly optimal.     «

The present paper introduces the geometric rank as a measure for the quality of relaxations of certain combinatorial optimization problems in the realm of polyhedral combinatorics. In particular, this notion establishes a tight relation between the maximum stable set problem from combinatorial optimization, polynomial programming from integer non linear programming and norm maximization, a basic problem from convex maximization and computational convexity. As a consequence we obtain very tigh...     »