TY - JOUR

T1 - Truthful mechanisms for combinatorial allocation of electric power in alternating current electric systems for smart grid

AU - Chau, Chi Kin

AU - Elbassioni, Khaled

AU - Khonji, Majid

N1 - Publisher Copyright:
© 2016 ACM.

PY - 2016/10

Y1 - 2016/10

N2 - Traditional studies of combinatorial auctions often only consider linear constraints. The rise of smart grid presents a new class of auctions, characterized by quadratic constraints. This article studies the complexdemand knapsack problem, inwhich the demands are complex valued and the capacity of supplies is described by the magnitude of total complex-valued demand. This naturally captures the power constraints in alternating current electric systems. In this article, we provide a more complete study and generalize the problem to the multi-minded version, beyond the previously known 1/2-approximation algorithm for only a subclass of the problem. More precisely, we give a truthful polynomial-time approximation scheme (PTAS) for the case φ ϵ [0, π/2-δ] and a truthful fully polynomial-time approximation scheme (FPTAS), which fully optimizes the objective function but violates the capacity constraint by at most (1 + ϵ), for the case φ ϵ ( π/2 , π - δ], where φ is the maximum argument of any complex-valued demand and ϵ δ > 0 are arbitrarily small constants. We complement these results by showing that, unless P=NP, neither a PTAS for the case φ ϵ ( π/2 , π - δ] nor any bi-criteria approximation algorithm with polynomial guarantees for the case when φ is arbitrarily close to π (that is, when δ is arbitrarily close to 0) can exist.

AB - Traditional studies of combinatorial auctions often only consider linear constraints. The rise of smart grid presents a new class of auctions, characterized by quadratic constraints. This article studies the complexdemand knapsack problem, inwhich the demands are complex valued and the capacity of supplies is described by the magnitude of total complex-valued demand. This naturally captures the power constraints in alternating current electric systems. In this article, we provide a more complete study and generalize the problem to the multi-minded version, beyond the previously known 1/2-approximation algorithm for only a subclass of the problem. More precisely, we give a truthful polynomial-time approximation scheme (PTAS) for the case φ ϵ [0, π/2-δ] and a truthful fully polynomial-time approximation scheme (FPTAS), which fully optimizes the objective function but violates the capacity constraint by at most (1 + ϵ), for the case φ ϵ ( π/2 , π - δ], where φ is the maximum argument of any complex-valued demand and ϵ δ > 0 are arbitrarily small constants. We complement these results by showing that, unless P=NP, neither a PTAS for the case φ ϵ ( π/2 , π - δ] nor any bi-criteria approximation algorithm with polynomial guarantees for the case when φ is arbitrarily close to π (that is, when δ is arbitrarily close to 0) can exist.

KW - Combinatorial power allocation

KW - Complex-demand knapsack problem

KW - Mechanism design

KW - Multi-unit combinatorial auctions

KW - Smart grid

UR - http://www.scopus.com/inward/record.url?scp=84979277417&partnerID=8YFLogxK

U2 - 10.1145/2955089

DO - 10.1145/2955089

M3 - Article

AN - SCOPUS:84979277417

SN - 2167-8375

VL - 5

JO - ACM Transactions on Economics and Computation

JF - ACM Transactions on Economics and Computation

IS - 1

M1 - 7

ER -