Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949519 | Discrete Applied Mathematics | 2017 | 15 Pages |
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 (1eâϵ)-approximation algorithm for submodular objective functions, for any ϵ>0, and a PTAS for quadratic objective functions where the underlying matrix has fixed nonnegative rank.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Khaled Elbassioni, Trung Thanh Nguyen,