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

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 article studies the 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 electric systems. In this article, we provide a more complete study and generalize the problem to the multi-minded version, beyond the previously known ½-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.