Open AccessApproximation Schemes for Two Non-Linear Knapsack Problems and Their Applications in Alternating Current Electric Systems
Author(s) -
Thanh Nam Nguyen
Publication year - 2017
Publication title -
journal of computer science and cybernetics (vietnam academy of science and technology)/journal of computer science and cybernetics
Language(s) - English
Resource type - Journals
eISSN - 2815-5939
pISSN - 1813-9663
DOI - 10.15625/1813-9663/33/2/10673
Subject(s) - knapsack problem , polynomial time approximation scheme , linear programming , approximation algorithm , mathematical optimization , mathematics , continuous knapsack problem , time complexity , constraint (computer aided design) , dual (grammatical number) , linear approximation , function (biology) , simple (philosophy) , polynomial , quadratic equation , discrete mathematics , physics , quantum mechanics , art , mathematical analysis , philosophy , geometry , literature , epistemology , nonlinear system , evolutionary biology , biology
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.