Truthful Mechanisms for Combinatorial Allocation of Electric Power in Alternating Current Electric Systems for Smart Grid

Chi-Kin Chau; Khaled Elbassioni; Majid Khonji

doi:10.1145/2955089

paper

Truthful Mechanisms for Combinatorial Allocation of Electric Power in Alternating Current Electric Systems for Smart Grid

arXiv:1507.01762 · doi:10.1145/2955089

Abstract

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 paper studies the {\em complex-demand knapsack problem}, in which 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 (AC) electric systems. In this paper, we provide a more complete study and generalize the problem to the multi-minded version, beyond the previously known $\frac{1}{2}$ -approximation algorithm for only a subclass of the problem. More precisely, we give a truthful PTAS for the case $ϕ \in [0, \frac{π}{2} - δ]$ , and a truthful FPTAS, which {\it fully} optimizes the objective function but violates the capacity constraint by at most $(1 + ε)$ , for the case $ϕ \in (\frac{π}{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 $ϕ \in (\frac{π}{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.

Extended version of AAMAS 14' paper arXiv:1403.3907

Truthful Mechanisms for Combinatorial Allocation of Electric Power in Alternating Current Electric Systems for Smart Grid

Abstract

References in corpus (2)

Cited by in corpus (6)