Approximation Schemes for Two Non-Linear Knapsack Problems and Their Applications in Alternating Current Electric Systems - Nguyen, Thanh (Journal of Computer Science and Cybernetics, 2017)
<!– p, li white-space: pre-wrap; –> <!–StartFragment–>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 p-hard since they generalize the unbounded Knapsack problem, and it is unlikely to obtain polynomial-time algorithms for them, unless = p. 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. <!–EndFragment–>