TAILIEUCHUNG - Approximation schemes for two non-linear knapsack problems arising in alternating current electric systems
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. | Journal of Computer Science and Cybernetics, , (2017), 165–179 DOI APPROXIMATION SCHEMES FOR TWO NON-LINEAR KNAPSACK PROBLEMS ARISING IN ALTERNATING CURRENT ELECTRIC SYSTEMS TRUNG THANH NGUYEN Hai Phong University; 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 algorithm uses a linear programming approach, which is common in the design of approximation schemes. Keywords. Complex power, alternating current electrical systems, integer quadratic programming, approximation scheme. 1. . INTRODUCTION Motivation and problem model The classical Knapsack problem and its variants naturally arise in modelling various practical applications such as computer networks, production planning, health care (see [7] and the references therein), and power allocation (see, ., [8, 9, 14]). Motivated by applications in electrical power production and allocation, in this paper we consider two non-linear Knapsack problems. The first problem, called Packing, is to maximize a nonnegative linear objective function subject to a nonlinear and .
đang nạp các trang xem trước
