


















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 in [0,pi/2-delta], and a truthful FPTAS, which fully optimizes the objective function but violates the capacity constraint by at most (1+epsilon), for the case phi in (pi/2,pi-delta], where phi is the maximum angle between any two complex-valued demands and epsilon,delta>0 are arbitrarily small constants.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。