Inapproximability of power allocation with inelastic demands in AC electric systems and networks

A challenge in future smart grid is how to efficiently allocate power among customers considering inelastic demands, when the power supply is constrained by the network or generation capacities. This problem is an extension to the classical knapsack problem in a way that the item values are expressed as non-positive real or complex numbers representing power demands, rather than positive real numbers. The objective is to maximize the total utility of the customers. Recently in Chau-Elbassioni-Khonji [AAMAS 14], a PTAS was presented for the case where the maximum phase angle between any pair of power demands is φ ≤ π/2; and a bi-criteria FPTAS when π/2 < φ ≤ π - ε, for any polynomially small ε. For 0 ≤ φ ≤ π/2, Yu and Chau [AAMAS 13] showed that unless P=NP, there is no FPTAS. In this paper, we present important hardness results that close the approximation gap. We show that unless P=NP, there is no α-approximation for π/2 < π ≤ π - ε, where a is any number with polynomial length. Moreover, for the case when φ is arbitrarily close to π, neither a PTAS nor any bi-criteria approximation algorithm with polynomial guarantees can exist. In this paper, we also present a natural generalization to a networked setting such that each edge in the transmission network can have a capacity constraint. We show that there is no bi-criteria approximation algorithm with polynomial guarantees for this networked setting, even all power demands are real (non-complex) numbers.