@inproceedings{74339d178d0445268f0adbacb346ab0c,
title = "Approximation schemes for multi-objective optimization with quadratic constraints of fixed CP-rank",
abstract = "Motivated by the power allocation problem in AC (alternating current) electrical systems, we study the multi-objective (combinatorial) optimization problem where a constant number of (nonnegative) linear functions are simultaneously optimized over a given feasible set of 0-1 points defined by quadratic constraints. Such a problem is very hard to solve if no specific assumptions are made on the structure of the constraint matrices. We focus on the case when the constraint matrices are completely positive and have fixed cp-rank. We propose a polynomial-time algorithm which computes an ϵ-Pareto curve for the studied multi-objective problem when both the number of objectives and the number of constraints are fixed, for any constant ϵ > 0. This result is then applied to obtain polynomial-time approximation schemes (PTASes) for two NP-hard problems: multi-criteria power allocation and sum-of-ratios optimization.",
author = "Khaled Elbassioni and Nguyen, {Trung Thanh}",
note = "Funding Information: We would like to thank Gerhard Woeginger for helpful discussions, especially for pointing us the papers [, ]. We thank the ADT-15 reviewers for their helpful comments, suggestions and insights that have helped us improve our manuscript. This work was supported by the MI-MIT Flagship project 13CAMA1. Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 4th International Conference on Algorithmic Decision Theory, ADT 2015 ; Conference date: 27-09-2015 Through 30-09-2015",
year = "2015",
doi = "10.1007/978-3-319-23114-3_17",
language = "British English",
isbn = "9783319231136",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "273--287",
editor = "Toby Walsh",
booktitle = "Algorithmic Decision Theory - 4th International Conference, ADT 2015, Proceedings",
address = "Germany",
}