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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations

Abstract

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.

Original languageBritish English
Title of host publication2014 23rd International Conference on Computer Communication and Networks, ICCCN Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781479935727
DOIs
StatePublished - 25 Sep 2014
Event2014 23rd International Conference on Computer Communication and Networks, ICCCN 2014 - Shanghai, China
Duration: 4 Aug 20147 Aug 2014

Publication series

NameProceedings - International Conference on Computer Communications and Networks, ICCCN
ISSN (Print)1095-2055

Conference

Conference2014 23rd International Conference on Computer Communication and Networks, ICCCN 2014
Country/TerritoryChina
CityShanghai
Period4/08/147/08/14

Keywords

  • Algorithms
  • Complex-Demand Knapsack Problem
  • Hardness Results
  • Smart Grid

Fingerprint

Dive into the research topics of 'Inapproximability of power allocation with inelastic demands in AC electric systems and networks'. Together they form a unique fingerprint.

Cite this