Approximating Quadratic 0-1 Programming via SOCP

Original · EN

We consider the problem of approximating Quadratic O-1 Integer Programs with bounded number of constraints and non-negative constraint matrix entries, which we term as PIQP. We describe and analyze a randomized algorithm based on a program with hyperbolic constraints (a Second-Order Cone Programming -SOCP- formulation) that achieves an approximation ratio of O(amax n/β(n)), where amax is the maximum size of an entry in the constraint matrix and β(n) ≤ ᵢWᵢ, where Wᵢ are the constant terms that define the constraint inequalities. We note that by appropriately choosing β(n) the randomized algorithm, when combined with other algorithms that achieve good approximations for smaller values of Wᵢ, allows better algorithms for the complete range of Wᵢ. This, together with a greedy algorithm, provides a O*(amax n¹/²) factor approximation, where O* hides logarithmic terms. Our solution is achieved by a randomization of the optimal solution to the relaxed version of the hyperbolic program. We show that this solution provides the approximation bounds using concentration bounds provided by Chernoff-Hoeffding and Kim-Vu.