Approximation schemes for two non-Linear knapsack problems arising in alternating current electric systems

Journal of Computer Science and Cybernetics, V.33, N.2 (2017), 165–179 DOI 10.15625/1813-9663/33/2/10673 APPROXIMATION SCHEMES FOR TWO NON-LINEAR KNAPSACK PROBLEMS ARISING IN ALTERNATING CURRENT ELECTRIC SYSTEMS TRUNG THANH NGUYEN Hai Phong University; ttnguyen.cs@gmail.com 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 1.1. 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, e.g., [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 non- linear and non-separable constraint, and the second one, called Covering, can be seen as a dual version of the first problem, where an objective is minimized. In what follows, we will give a brief overview of the applications of these two problems as well as their mathematical formulations. 1.1.1. Maximizing the profit of users Recently, Yu and Chau [17] introduced a non-linear Knapsack problem called complex-demand knapsack problem, to capture the power allocation in alternating current (AC) electrical systems, where each electrical device (user) has a power demand expressed as a complex number d = dR+idI , and there is a limit on the magnitude of total power supply. Since only a limited number of devices can be served and different devices produce different profits when they receive enough power to work, there arises a natural allocation problem: we want to maximize the sum of profits of the chosen c© 2017 Vietnam Academy of Science & Technology 166 TRUNG THANH NGUYEN users such that the magnitude of the sum of satisfied demands should not exceed the capacity. For a complex demand d, the real part dR represents the active power and the imaginary part dI represents the reactive power. The apparent power |d| = √ (dR)2 + (dI)2 is the magnitude of the complex power d. Therefore, the system capacity can be formulated through a quadratic constraint and, in fact, the power allocation can be mathematically modeled as an integer quadratic programming problem. In this paper we consider the complex-demand knapsack problem in a setting where we allow each user to be able to have more than one complex demand. The problem can be formulated as follows. Packing max n∑ k=1 ukxk (1) subject to ( n∑ k=1 dRk xk )2 + ( n∑ k=1 dIkxk )2 ≤ C2. (2) x ∈ Zn+, (3) where dk = (d R, dI) ∈ Z2+ is an unit complex demand of power of the k-th user, C ∈ Z+ is a real-valued capacity of total satisfiable demand in apparent power, and uk ∈ Z+ is the profit of the k-th user if the unit demand is satisfied. 1.1.2. Minimizing the cost of electrical power generation The dual version of the Packing problem above can be used to model the Unit Commitment Problem [12] in electrical power production, where the production of a set of electrical generators is coordinated in order to match the energy demand at minimum cost from energy production. There are two common types of cost factors that can be taken into account to measure the cost of electrical power generation, including capital cost and carbon pricing. Intuitively, the capital costs can be seen as the payment for the purchase of land, buildings, construction, and equipment used in the production of electricity, and this cost may vary depending on the type of power plants. Particularly, it is typically low for fossil fuel power stations, yet high for wind turbines, and become very high for other ways of generating electricity, such as waste to energy, wave and tidal, solar thermal, and nuclear. The carbon pricing is indirectly borne by society as a whole as a consequence of using that energy source. For example, most electricity today is generated by burning fossil fuels and this process results in the transformation of carbon dioxide (CO2), which is then released into the air. Hence, the carbon pricing could be seen as the cost of fossil fuel generation, which charges those who produce CO2 from their emissions, and thus is a necessary part of policies that can reduce the global-warming emissions. Now lets imagine that we have a project that aims to build up a number of different power plants for the generation of electrical power in such a way that the total electrical power generated (i.e., the supply) must be not less than a threshold reflecting the demand on energy consumption, while the total cost induced by the generation is minimized. In order to minimize the total cost of electrical power generation, the decision maker has to decide how many power stations should be constructed, and what type of power stations should be. This problem can be mathematically modeled as an integer non-linear programming, in which one needs to minimize a linear cost function subject to APPROXIMATION SCHEMES FOR TWO NON-LINEAR KNAPSACK PROBLEMS 167 a quadratic constraint expressing the constraint on the total power generated. The mathematical formulation of the problem is as follows. Covering min n∑ k=1 ckxk, (4) subject to ( n∑ k=1 dRk xk )2 + ( n∑ k=1 dIkxk )2 ≥ C2, (5) x ∈ Zn+, (6) where n is the number of different types of power plants needed to build. For the power plant of type k ∈ {1, . . . , n}, the variable xk represents the number of alternating current generators that the power plant can have, and each generator can produce an amount of power specified by a complex number dk = d R k + id I k, and induces a cost ck. The nonnegative number C represents the energy demand. 1.2. Related work Although the complex-demand Knapsack problem was introduced recently by Yu and Chau [17] along with an important application in smart grid, it was actually studied for the first time by Woeginger [15, 16] almost twenty years ago, but in a different name, 2-weighted Knapsack problem. In his paper, Woeginger ruled out the existence of fully polynomial time approximation schemes for the problem, unless P = NP. Yu and Chau [17] gave a first (12 − )-approximation algorithm for any small constant  > 0. A simple greedy 1 2 √ 2 -approxiamtion algorithm with running time O(n log n) was presented recently in [6]. Chau et al. [1, 2] settled the approximability status of the problem by providing a PTAS for the problem, their method makes use of the PTAS for the multi-dimensional Knapsack problem as a subroutine. Very recently, Elbassioni and Nguyen [3, 4] extended the study to more general problems with non-linear objective functions such as fractional functions, submodular functions, and quadratic functions of fixed nonnegative rank. 1.3. Our contribution and technique Packing and Covering belong to the class of integer quadratic programming, and are NP- hard as they generalize the (unbounded) Knapsack problem [7]. This means they cannot be solved in polynomial time, under the standard assumption P 6= NP. It is therefore important to look for efficient approximation algorithms with a good guarantee approximation. Our contribution of this paper is to propose the first PTASs for Packing and Covering, which are the best possible results we can hope for these problems. Note that the greedy approach in [6], the geometry approach in [2], and the linear programming approach in [4] are for a variant of the Packing problem with binary variables, and only the last approach can be extended to the setting with integer variable, as shown in our paper, to yield a PTAS with the same time complexity. The theorems below summarize our results. Theorem 1. Given a problem instance of Packing, there is an algorithm that runs in polynomial time in the size of the instance and returns a solution of value of at least 1 −  times the optimum, for any fixed constant  > 0. 168 TRUNG THANH NGUYEN Theorem 2. Given a problem instance of Covering, there is an algorithm that runs in polynomial time in the size of the instance and returns a solution of value of at most 1 +  times the optimum, for any fixed constant  > 0. 1.4. Basic notions on approximation algorithms For α ∈ (0, 1], a vector x ∈ Zn+ is said to be an α-approximate solution for problem Packing (resp., Covering), if x is a feasible solution satisfying n∑ k=1 ukxk ≥ α · Opt (resp., n∑ k=1 ckxk ≤ (1/α) ·Opt), where Opt is the value of an optimal solution. A PTAS for problem Packing (resp., Covering) is an algorithm that runs in polynomial time in the input size, for every fixed , and outputs an (1−)-approximate solution (resp., (1+)-approximate solution). An FPTAS is a PTAS whose running time is also polynomial in 1/. Throughout this paper, we will sometimes write uTx and cTx instead of n∑ k=1 ukxk and n∑ k=1 ckxk, respectively, where v T denotes the transpose of the vector v. 2. APPROXIMATION SCHEME FOR PACKING In this section we give a proof for Theorem 1. Let  > 0 be a fixed constant, and I be a problem instance of Packing, we will show that the Algorithm 1 below runs in polynomial time and outputs a solution z such that uT z ≥ (1− )Opt, where Opt denotes the value of an optimum of I. Throughout this paper, to simplify the presentation, we call items instead of users or devices or power plants. Let λ be some constant depending on  and it exact value will be determined later. Without loss of generality, we can assume that u1 ≥ u2 ≥ . . . ≥ un. The idea, extending the one in [5], is to try to guess the λ items of highest utility (profit) in the optimal solution. This can be done by considering all possibilities of choosing a vector s = (s1, . . . , sn) ∈ Zn+ such that n∑ i=1 si ≤ λ and ( n∑ k=1 dRk sk )2 + ( n∑ k=1 dIksk )2 ≤ C2. (7) The constraint (7) needs to be satisfied by the vector s since otherwise, s will not be part of the optimum solution. Let X be the set containing all such vectors s. It is easy to see that the size of X is bounded by O(nλ), which is polynomial in n for every constant λ. Therefore, we can guess exactly the λ items of highest utility in the optimum in polynomial time, by running over all vectors s ∈ X . Now, for each s ∈ X , denote m as the largest positive integer for which sm 6= 0, and let U = m∑ k=1 dRk sk, and V = m∑ k=1 dIksk. (8) If si = 0 for all i = 1, . . . , n then set m = 0. We next consider the following problem APPROXIMATION SCHEMES FOR TWO NON-LINEAR KNAPSACK PROBLEMS 169 IP(s) max n∑ k=m ukxk, (9) subject to ( U + n∑ k=m dRk xk )2 + ( V + n∑ k=m dIkxk )2 ≤ C2, (10) x ∈ Zn−m+1+ . (11) Let us define CR(s) as a convex relaxation of the IP(s), which is obtained from IP(s) by replacing the constraint x ∈ Zn−m+1+ by x ∈ Rn−m+1+ . Note that CR(s) is feasible due to (7). Furthermore, since CR(s) is convex, its optimal solution y can be found via polynomial-time algorithms for convex programming (see, e.g., [11]). CR(s) max n∑ k=m ukxk, (12) subject to ( U + n∑ k=m dRk xk )2 + ( V + n∑ k=m dIkxk )2 ≤ C2, (13) x ∈ Rn−m+1+ . (14) Algorithm 1 Packing-PTAS Require: A utility vector u ∈ Zn+; demands dk = (dRk , dIk) ∈ Z2+, k ∈ {1, . . . , n}; a capacity C; and accuracy parameter  Ensure: A solution v such that uT v ≥ (1− )Opt 1: Order the xk’s such that u1 ≥ . . . ≥ un 2: v ← (0, . . . , 0) 3: λ← ⌈3 ⌉ 4: X ← {(s1, . . . , sn) ∈ Zn+| n∑ k=1 sk ≤ λ} 5: for each s = (s1, . . . , sn) ∈ X do 6: m← max{i ∈ [n]|si 6= 0} 7: Construct CR(s) 8: Return y as an optimal solution of CR(s) 9: Construct the convex polytope P(s) 10: Find a BFS z 11: x← (s1, . . . , sm−1, sm + bzmc , bzm+1c , . . . , bznc) 12: if n∑ k=1 ukxk > n∑ k=1 ukvk then 13: v ← x 14: return v Define α = n∑ k=m dRk yk, and β = n∑ k=m dIkyk, (15) 170 TRUNG THANH NGUYEN and γ = n∑ k=m (UdRk + V d I k)yk. (16) Let P(s) be a (convex) polytope in Rn−m+1+ , defined by the system of following linear constraints n∑ k=m dRk xk ≤ α (17) n∑ k=m dIkxk ≤ β (18) n∑ k=m (UdRk + V d I k)xk ≤ γ (19) xk ≥ 0, for k = m, . . . , n. (20) Note that P(s) is a non-empty set as it contains y as a point. Therefore, we can find in polynomial time a basic feasible solution (BFS) z in this polytope such that z has at most 3 nonzero components and that n∑ k=m ukzk ≥ n∑ k=m ukyk, (21) (see, e.g., [13, 10]). We then round-down z to obtain an integral solution (bzmc , bzm+1c , . . . , bznc), and this solution is combined with the vector s to result in an integral solution x to the problem instance I: x = (s1, . . . , sm−1, sm + bzmc , bzm+1c , . . . , bznc). For each vector s ∈ X , the algorithm outputs a corresponding integral solution x. Let v be the solution of maximum value among all such solutions x, and return v as a final solution. Lemma 1. Algorithm 1 runs in polynomial time and produces a solution whose value is at least a fraction of (1− ) of the optimum. Proof. From the argument above, it can be easily seen that the running time of the Algorithm 1 is polynomial in the size of the input, for any fixed constant . Let x∗ = (x∗1, . . . , x∗n) be an optimal solution to the instance I, and let Opt = uTx∗. We now argue that the solution v returned by the algorithm is such that uT v ≥ (1− )Opt. If λ ≥ n∑ k=1 x∗k, then v is an exact optimal solution to the I (this is because of the guessing step). Suppose that λ < n∑ k=1 x∗k. Let s = (s1, . . . , sm, . . . , sn) be the vector such that i) n∑ k=1 sk = λ, ii) sm 6= 0 and sk = 0 for all k = m+ 1, . . . , n, iii) sk = x ∗ k for all k = 1, . . . ,m− 1. Clearly, s ∈ X . Then, the feasibility of x∗ for CR(s) guarantees that (7) holds, and hence an optimal solution y to CR(s) is found in Step 8 of the algorithm. Furthermore, the feasibility of y for APPROXIMATION SCHEMES FOR TWO NON-LINEAR KNAPSACK PROBLEMS 171 CR(s) implies that ( U + n∑ k=m dRk yk )2 + ( V + n∑ k=m dIkyk )2 = U2 + V 2 + ( n∑ k=m dIkyk )2 + ( n∑ k=m dRk yk )2 +2U · ( n∑ k=m dIkyk ) + 2V · ( n∑ k=m dRk yk ) ≤ C2, or, α2 + β2 + 2γ ≤ C2 − U2 − V 2, (22) where α, β, γ, U, V are defined as in (8), (15), and (16). Moreover, the definition of α, β, γ implies that y ∈ P(s). This means P(s) is nonempty and thus, there must be a BFS z of P(s) such that∑n k=m ukzk ≥ ∑n k=m ukyk. Let x ∈ Zn+ be the rounded solution obtained from z in Step 11. We have n∑ k=1 ukvk ≥ n∑ k=1 ukxk = m−1∑ k=1 ukxk + n∑ k=m ukxk. (23) Since (xm, xm+1, . . . , xn) is obtained by rounding down z and the fact that z has at most three nonzero components, it follows that n∑ k=m ukxk ≥ umsm + n∑ k=m ukzk − 3um (24) Note that u1 ≥ . . . ≥ un, it follows that 3um = 3um · 1 λ m∑ k=1 sk ≤ 3 λ m∑ k=1 uksk, (25) since λ = n∑ k=1 sk = m∑ k=1 sk By choosing λ = ⌈ 3  ⌉ , it follows that 3 λ ≤ , and that 3um ≤  m−1∑ k=1 ukxk + umsm, (26) 172 TRUNG THANH NGUYEN From (23), (24), and (26) we have n∑ k=1 ukvk ≥ n∑ k=1 ukxk ≥ m−1∑ k=1 ukxk + umsm −  m−1∑ k=1 ukxk − umsm + n∑ k=m ukzk ≥ (1− ) ( m−1∑ k=1 ukxk + umsm + n∑ k=m ukzk ) ≥ (1− ) ( m−1∑ k=1 ukxk + umsm + n∑ k=m ukyk ) ≥ (1− ) ( m−1∑ k=1 ukxk + n∑ k=m ukx ∗ m ) = (1− )Opt. It remains to argue that x (and thus v) is feasible for Packing. Let T = ( n∑ k=1 dRk xk )2 + ( n∑ k=1 dIkxk )2 , we prove that T ≤ C2. Indeed, we transform T as follows: T = ( m∑ k=1 dRk sk )2 + ( m∑ k=1 dIksk )2 + ( n∑ k=m+1 dRk xk + d R m bzmc )2 + ( n∑ k=m+1 dIkxk + d I m bzmc )2 +2 ( m∑ k=1 dRk sk ) · ( n∑ k=m+1 dRk xk + d R m bzmc ) + 2 ( m∑ k=1 dIksk ) · ( n∑ k=m+1 dIkxk + d I m bzmc ) . Since z ∈ P(s), and xk ≤ zk for all k ≥ m+ 1, it follows that n∑ k=m+1 dRk xk + d R m bzmc ≤ n∑ k=m dRk zk ≤ α, and n∑ k=m+1 dIkxk + d I m bzmc ≤ n∑ k=m dIkzk ≤ β. Therefore, T ≤ U2 + V 2 + α2 + β2 + 2γ ≤ C2. The last inequality follows from (22). This completes the proof.  APPROXIMATION SCHEMES FOR TWO NON-LINEAR KNAPSACK PROBLEMS 173 3. APPROXIMATION SCHEME FOR COVERING This section is devoted to presenting a proof of Theorem 2, which claims the existence of a polynomial time approximation scheme for the Covering problem. Basically, the main idea for designing such a scheme is not very different from the one for the Packing problem in the previous section, which relies on the polynomial time solvability of the convex relaxation CR(s). However, a similar relaxation (see below) for Covering is no longer convex due to the non-convexity of the quadratic constraint. Consequently, the current techniques known for solving exactly convex problems in polynomial time cannot be applied to the case of Covering. (NCR) max n∑ k=1 ckxk, (27) subject to ( n∑ k=1 dRk xk )2 + ( n∑ k=1 dIkxk )2 ≥ C2, (28) x ∈ Rn+, (29) Fortunately, by using a the KKT conditions, one can show that the global optimum to the non-convex relaxation NCR above can be found in polynomial time. Theorem 3. One can find an optimal solution z to the problem NCR in polynomial time. Furthermore, z has at most two non-zero components. Proof. To simplify the notations, let dRk = ak and d I k = bk for all k = 1, . . . , n. Without of loss generality we can assume that there is no pair of indices (i, j) such that ai aj = bi bj = ci cj . (30) The argument is as follows. Suppose that the condition (30) holds for some i 6= j. Let ai = `aj , bi = `bj , and ci = `cj for some positive integer `. By reordering the variables (if necessary) we can assume that i = n− 1, j = n. Hence, the objective function of NCR and the constraint (28) can be rewritten, respectively, in the following forms: n−2∑ k=1 ckxk + cny, and, ( n−2∑ k=1 akxk + any )2 + ( n−2∑ k=1 bkxk + bny )2 ≥ C2, where y = `xn−1 + xn. This means that the problem NCR is reduced to a similar problem, but with a smaller number of variables. By repeating the same reduction until the condition (30) is not satisfied for all i 6= j, we obtain a reduced problem which are equivalent to NCR, and we can therefore solve this problem instead of NCR. 174 TRUNG THANH NGUYEN We are now ready to prove the Theorem 3. Let us define the Lagrangian function L(x, λ, µ) = n∑ k=1 ckxk − n∑ k=1 µkxk + λ C2 − ( n∑ k=1 akxk )2 − ( n∑ k=1 bkxk )2 , where λ, µ = (µ1, . . . , µn) are called Lagrange multipliers, and x = (x1, . . . , xn). It is known that every local solution to NCR must satisfy the following Karush-Kuhn-Tucker (KKT) conditions ∂L(x, λ, µ) ∂xk = 0, for k = 1, . . . , n, (31) λ C2 − ( n∑ k=1 akxk )2 − ( n∑ k=1 bkxk )2 = 0, (32) C2 − ( n∑ k=1 akxk )2 − ( n∑ k=1 bkxk )2 ≤ 0, (33) λ ≥ 0, (34) µkxk = 0, k = 1, . . . , n, (35) µk ≥ 0, k = 1, . . . , n, (36) xk ≥ 0, k = 1, . . . , n. (37) A feasible solution to NCR which satisfies the system of equations above is called a KKT point (or a stationary point). Since every optimal point needs to be among the KKT points, in order to find an optimal point, we just need to maximize the objective function over all possible KKT points. This task in general is impossible because of the two reasons: first, the number of KKT points could be exponential; and second, determining KKT points might be very hard. In what follows, however, we will show that there is a polynomial number of KKT points, which can be determined efficiently, for the system of equations (31)-(37) and thus, the optimal point can be found easily. The equations (31) is equivalent to ck − 2λ ( ak n∑ k=1 akxk + bk n∑ k=1 akxk ) − µk = 0, (38) for k = 1, . . . , n. Let X = 2λ n∑ k=1 akxk and Y = 2λ n∑ k=1 bkxk. (39) Then the equations (38) can be written as akX + bkY + µk = ck, (40) for k = 1, . . . , n. Now if λ = 0, it follows that µk = ck 6= 0 due to (31), and by (35) xk = 0 for all k, but this violates the constraint (33). Hence, λ > 0, and there must be at least one variable of positive value. APPROXIMATION SCHEMES FOR TWO NON-LINEAR KNAPSACK PROBLEMS 175 Furthermore, the constraint (32) implies that C2 = ( n∑ k=1 akxk )2 + ( n∑ k=1 bkxk )2 = ( X 2λ )2 + ( Y 2λ )2 . (41) We now can find a set S of all KKT points as follows. It is sufficient to consider the following cases: Case I: All variables µk are non-zero. Case II: There is exactly one zero variable µk. Case III: There are at least two zero variables µi, µj . In the case I, it follows from (35) that xk = 0 for all k = 1, . . . , n, but then the zero vector (0, . . . , 0) is not feasible to NCR. For the case II, there are in total n possibilities for choosing a zero variable µk. In fact, for k ∈ {1, . . . , n}, the kth possibility is that µk = 0 and µi 6= 0 for all i 6= k. Again, this follows from (35) that xi = 0 for all i 6= k, and we thus need to check if a vector of the form (0, . . . , 0, xk, 0, . . . , 0) is a solution of the system (31)-(37). If yes, we add it, with the determined value of xk, into the set S. For the case III, there are in total ( n 2 ) possibilities of choosing two zero variables (µi, µj), i 6= j. For each such a possibility (µi, µj), the inequalities (40) result in the following equations aiX + biY = ci, (42) ajX + bjY = cj . (43) Note that by our early assumption (which says that there is no pair (i, j) satisfying (30)) it holds that the system (42)-(43) either has no solution or has only one solution of the form X = cibj − cjbi aibj − ajbi , Y = aicj − ajci aibj − ajbi . (44) Substituting (44) into (40) and (41) we can easily find the values of λ and µk for all k. Additionally, the values of ∑n k=1 akxk and ∑n k=1 bkxk can be determined by the equalities (38). We further check if these values satisfy all other KKT conditions and if yes, we solve the following problem min ∑n k=1 ckxk, (45) subject to ∑n k=1 akxk = X/2λ, (46)∑n k=1 bkxk = Y/2λ, (47) x ∈ Rn+, (48) xk = 0 if µk 6= 0, (49) which, in fact, can be thus solved in polynomial time. The optimal solution found is then put into S. Note that this optimal solution has at most two non-zero components since there are only two non-trivial linear constraints (46) and (47). 176 TRUNG THANH NGUYEN Finally, the optimal solution z to the problem NCR is computed as z = argx∈S n∑ k=1 ckxk. Note that since the size of S is at most n + ( n 2 ) = O(n2), z can be computed in polynomial time. Furthermore, it is observed that z also has at most two non-zero components. This completes the proof of Theorem 3.  Turning to the proof of Theorem 2, let us consider the following Algorithm 2. Algorithm 2 Covering-PTAS Require: A cost vector c ∈ Zn+; demands dk = (dRk , dIk) ∈ Z2+, k ∈ {1, . . . , n}; a capacity C; and accuracy parameter  Ensure: A solution v such that cT v ≤ (1 + )Opt 1: Order the xk’s such that c1 ≥ . . . ≥ cn 2: v ← (1, . . . , 1) 3: λ← ⌈2 ⌉ 4: X ← {(s1, . . . , sn) ∈ Zn+| ∑n k=1 sk ≤ λ} 5: for each s = (s1, . . . , sn) ∈ X do 6: m← max{i ∈ [n]|si 6= 0} 7: Construct NCR(s) 8: Return z as an optimal solution of CR(s), which has at most two non-zero components 9: x← (s1, . . . , sm−1, sm + dzme , dzm+1e , . . . , dzne) 10: if ∑n k=1ckxk < ∑n k=1ckvk then 11: v ← x 12: return v Lemma 2. For any fixed  > 0, Algorithm 2 runs in polynomial time and produces a solution whose value is at most a fraction of 1 +  of the optimum. Proof. The proof is essentially the same as the one given for Algorithm 1. Let λ = ⌈ 2  ⌉ . The quantities U, V with respect to a vector s ∈ X are defined in a same way as before. The non-convex relaxation NCR(s) is NCR(s) max n∑ k=m ckxk, (50) subject to ( U + n∑ k=m dRk xk )2 + ( V + n∑ k=m dIkxk )2 ≥ C2, (51) x ∈ Rn−m+1+ . (52) Let x∗ = (x∗1, . . . , x∗n) be an optimal solution to the instance I of Covering, and let Opt = cTx∗. We now argue that the solution v returned by the algorithm is such that cT v ≤ (1 + )Opt. If λ ≥ n∑ k=1 x∗k, then we are done. Suppose that λ < n∑ k=1 x∗k. Let s = (s1, . . . , sm, . . . , sn) be the vector such that APPROXIMATION SCHEMES FOR TWO NON-LINEAR KNAPSACK PROBLEMS 177 i) n∑ k=1 sk = λ, ii) sm 6= 0 and sk = 0 for all k = m+ 1, . . . , n, iii) sk = x ∗ k for all k = 1, . . . ,m− 1. We have that n∑ k=1 ckvk ≤ n∑ k=1 ckxk = m−1∑ k=1 ckxk + n∑ k=m ckxk. (53) Note that this time (xm, xm+1, . . . , xn) is obtained by rounding up z, and by the fact that z has at most two non-zero components, it follows that n∑ k=m ckxk ≤ cmsm + n∑ k=m ckzk + 2cm. (54) Note that c1 ≥ . . . ≥ cn, it follows that 2um = 2cm · 1 λ m∑ k=1 sk ≤ 2 λ m∑ k=1 cksk =  m−1∑ k=1 ckxk + cmsm, (55) since λ = n∑ k=1 sk = m∑ k=1 sk, From (53), (54), and (55) we have n∑ k=1 ckvk ≤ n∑ k=1 ckxk ≤ m−1∑ k=1 ckxk + cmsm +  m−1∑ k=1 ckxk + cmsm + n∑ k=m ckzk ≤ (1 + ) ( m−1∑ k=1 ckxk + cmsm + n∑ k=m ckzk ) ≤ (1 + ) ( m−1∑ k=1 ckxk + n∑ k=m ckx ∗ k ) = (1 + )Opt. The feasibility of x (and v) to the Covering problem can be treated in a similar way as in the case of Packing. This completes the proof.  4. CONCLUSION In this paper we have presented the first PTASs for the two non-linear Knapsack problems, Pack- ing and Covering, which are motivated by applications in alternating current electrical systems. Since these two problems are NP-hard, the obtained PTASs are the best possible approximation 178 TRUNG THANH NGUYEN algorithms, assuming that P 6= NP. Although the PTAS is of theoretical interest, it is quite imprac- tical as the running time is exponential in the constant 1 . Our work raises several open problems for the future work. The first problem is to check whether we can achieve a PTAS for Covering with binary variables. The technique used in this paper, which relies on the KKT conditions, does not help to solve the (non-convex) relaxation of the problem in the binary setting. Another open problem is to extend our PTASs to the case where the constraint involves more than two squares of linear functions. Finally, it would be very interesting to develop more practical approximation algorithms for both Packing and Covering. For example, it is worth seeing if the greedy approach provided in [6] yields an approximation algorithm with the same approximation factor of 1 2 √ 2 . Acknowledgments We would like to thank Khaled Elbassioni and Gerhard Woeginger for helpful discussion on the problem. Also, we would like to thank the reviewers for all the very helpful comments, which helped to much improve the presentation of the paper. This work was supported by Vietnam National Foundation for Science and Technology Development (NAFOSTED Project No. 102.01-2015.33). REFERENCES [1] C. Chau, K. M. Elbassioni, and M. Khonji, “Truthful mechanisms for combinatorial allocation of electric power in alternating current electric systems for smart grid,” ACM Trans. Economics and Comput., vol. 5, no. 1, p. 7, 2016. [2] S. C. Chau, K. M. Elbassioni, and M. Khonji, “Truthful mechanisms for combinatorial AC electric power allocation,” in International conference on Autonomous Agents and Multi-Agent Systems, AAMAS ’14, Paris, France, May 5-9, 2014, 2014, pp. 1005–1012. [3] K. M. Elbassioni and T. T. Nguyen, “Approximation schemes for multi-objective optimization with quadratic constraints of fixed cp-rank,” in Algorithmic Decision Theory - 4th International Conference, ADT 2015, Lexington, KY, USA, September 27-30, 2015, Proceedings, 2015, pp. 273–287. [4] ——, “Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions,” Discrete Applied Mathematics, vol. 230, pp. 56–70, 2017. [5] A. Frieze and M. Clarke, “Approximation algorithms for the m-dimensional 0-1 knapsack prob- lem: worst-case and probabilistic analyses,” Eur. J. Oper. Res., vol. 15, pp. 100–109, 1984. [6] A. Karapetyan, M. Khonji, C. Chau, K. M. Elbassioni, and H. H. Zeineldin, “Efficient algorithm for scalable event-based demand response management in microgrids,” IEEE Transactions on Smart Grid, doi: 10.1109/TSG.2016.2616945. To appear. [7] H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems. Springer, Berlin, Germany, 2004. [8] N. Kumaraguruparan, H. Sivaramakrishnan, and S. S. Sapatnekar, “Residential task scheduling under dynamic pricing using the multiple knapsack method,” in IEEE PES Innovative Smart Grid Technologies Conference, ISGT 2012, Washington, DC, USA, January 16-20, 2012, 2012, pp. 1–6. APPROXIMATION SCHEMES FOR TWO NON-LINEAR KNAPSACK PROBLEMS 179 [9] N. Morimoto, Y. Fujita, M. Yoshida, H. Yoshimizu, M. Takiyamada, T. Akehi, and M. Tanaka, “A power allocation management system using an algorithm for the knapsack problem,” in IEEE 38th Annual Computer Software and Applications Conference, COMPSAC Workshops 2014, Vasteras, Sweden, July 21-25, 2014, 2014, pp. 590–595. [10] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization. New York, NY, USA: Wiley-Interscience, 1999. [11] A. Nemirovski and M. Todd, “Interior-point methods for optimization,” Acta Numerica, vol. 17, pp. 191–234, 5 2008. [12] N. Padhy, “Unit commitment − a bibliographical survey,” IEEE Transaction On Power Systems, vol. 19, no. 2, pp. 1196–1205, 2004. [13] A. Schrijver, Theory of Linear and Integer Programming. New York: Wiley, 1986. [14] O. A. Sianaki, O. Hussain, and A. R. Tabesh, “A knapsack problem approach for achieving efficient energy consumption in smart grid for endusers’ life style,” in 2010 IEEE Conference on Innovative Technologies for an Efficient and Reliable Electricity Supply (CITRES), 2010, pp. 159–164. [15] G. J. Woeginger, “When does a dynamic programming formulation guarantee the existence of an fptas?” in Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland., 1999, pp. 820–829. [16] ——, “When does a dynamic programming formulation guarantee the existence of a fully poly- nomial time approximation scheme (FPTAS)?” INFORMS Journal on Computing, vol. 12, no. 1, pp. 57–74, 2000. [17] L. Yu and C. Chau, “Complex-demand knapsack problems and incentives in AC power systems,” in International conference on Autonomous Agents and Multi-Agent Systems, AAMAS ’13, Saint Paul, MN, USA, May 6-10, 2013, 2013, pp. 973–980. Received on September 14, 2017 Revised on November 10, 2017