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.
展开▼
