Approximation Schemes for Two Non-Linear Knapsack Problems and Their Applications in Alternating Current Electric Systems

Abstract

The purpose of this paper is to study the approximability of two non-linear Knapsack problems, which are motivated by important applications in alternating current electrical systems. The first problem is to maximize a nonnegative linear objective function subject to a quadratic constraint, whilst the second problem is a dual version of the first one, where an objective function is minimized. Both problems are $\np$-hard since they generalize the unbounded Knapsack problem, and it is unlikely to obtain polynomial-time algorithms for them, unless $\p=\np$. It is therefore of great interest to know whether or not there exist efficient approximation algorithms which can return an approximate solution in polynomial time with a reasonable approximation factor. Our contribution of this paper is to present polynomial-time approximation schemes (PTASs) and this is the best possible result one can hope for the studied problems. Our technique is based on the linear-programming approach which seems to be more simple and efficient than the previous one.