2014/11/18 by Khaled Elbassioni, Trung Thanh Nguyen, Elbassioni, Khaled +1
Engineering · Computer Science · #Optimization and Packing Problems #Optimization and Search Problems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.1411.5050
Binary quadratic programming problems have attracted much attention in the last few decades due to their potential applications. This type of problems are NP-hard in general, and still considered a challenge in the design of efficient approximation algorithms for their solutions. The purpose of this paper is to investigate the approximability for a class of such problems where the constraint matrices are \it completely positive and have low \it cp-rank. In the first part of the paper, we show that a completely positive rational factorization of such matrices can be computed in polynomial time, within any desired accuracy. We next consider binary quadratic programming problems of the following form: Given matrices Q1,...,Qn∈ℝ+n× n, and a system of m constrains xTQix≤ Ci2 (xTQix≥ Ci2), i=1,...,m, we seek to find a vector x^*∈ \0,1\n that maximizes (minimizes) a given function f. This class of problems generalizes many fundamental problems in discrete optimization such as packing and covering integer programs/knapsack problems, quadratic knapsack problems, submodular maximization, etc. We consider the case when m and the cp-ranks of the matrices Qi are bounded by a constant. Our approximation results for the maximization problem are as follows. For the case when the objective function is nonnegative submodular, we give an (1/4-ε)-approximation algorithm, for any ε>0; when the function f is linear, we present a PTAS. We next extend our PTAS result to a wider class of non-linear objective functions including quadratic functions, multiplicative functions, and sum-of-ratio functions. The minimization problem seems to be much harder due to the fact that the relaxation is \it not convex. For this case, we give a QPTAS for m=1.