Truthful Mechanisms for Combinatorial AC Electric Power Allocation

Abstract

Traditional studies of combinatorial auctions often only consider linear constraints (by which the demands for certain goods are limited by the corresponding supplies). The rise of smart grid presents a new class of auctions, characterized by quadratic constraints. Yu and Chau [AAMAS '13] introduced 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 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 1/2-approximation algorithm for only a subclass of the problem. More precisely, we give a truthful PTAS for the case phi is an element of the set [0, pi/2], and a truthful bi-criteria FPTAS for the general case phi is an element of the set (pi/2, pi-epsilon], where phi is the maximum angle between any two complex-valued demands.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 2014
Accession Number
ADA601739

Entities

People

  • Chi-kin Chau
  • Khaled Elbassioni
  • Majid Khonji

Organizations

  • Masdar

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Accuracy
  • Algorithms
  • Alternating Current
  • Autonomous Agents
  • Behavioral Sciences
  • Boundaries
  • Complex Numbers
  • Computer Programming
  • Dynamic Programming
  • Electric Power
  • Multiagent Systems
  • Numbers
  • Polynomials
  • Power
  • Quadrants
  • Social Welfare

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Operations Research
  • Plasma Physics / Magnetohydrodynamics