کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949519 | 1440193 | 2017 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions](/preview/png/4949519.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 230, 30 October 2017, Pages 56-70
Journal: Discrete Applied Mathematics - Volume 230, 30 October 2017, Pages 56-70
نویسندگان
Khaled Elbassioni, Trung Thanh Nguyen,