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

arXiv: https://arxiv.org/abs/1507.01762 · HTML: https://mlsanity.com/paper/1507.01762/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2015.

## Built on by (most cited first, 1 of 1)

- [A Fully Polynomial Time Approximation Scheme for Constrained MDPs and Stochastic Shortest Path under Local Transitions](https://mlsanity.com/paper/2204.04780/) (2022)

## Abstract (arXiv)

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 frac12-approximation algorithm for only a subclass of the problem. More precisely, we give a truthful PTAS for the case φ∈[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 φ∈(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 φ∈(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.