Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions

摘要

Abstract The aim of this paper is to study approximation algorithms for a class of binary packing problems with quadratic constraints, where the constraint matrices are completely positive and have low cp-rank. We show that limiting the cp-rank makes the quadratic optimization problem exhibit similar approximability behavior as the linear case, assuming a constant number of quadratic constrains. We first show a convex programming-based method that yields a polynomial-time approximation scheme (PTAS) for the problem with linear objective functions. For non-linear objective functions, we follow a geometry-based approach to design approximation algorithms for a class of functions fulfilling certain conditions. Particularly, we obtain a ( 1 e ? ? ) -approximation algorithm for submodular objective functions, for any ?