Truthful Complex-valued Knapsack Problem and Discrete Optimization in A/C Electrical Grid
Chi-Kin Chau, Lan Yu · arXiv (Cornell University) · 2012
Since efficient power allocation is a critical requirement for smart grid, we study an important basic setting -- problem with selfish users, whereby we design a mechanism to find a utility-maximizing allocation for a group of users with inelastic demands, such that users truthfully reveal their private utility information. As a departure from the traditional setting, complex-valued entities (e.g. power, voltage, and current) are common in A/C electrical grid. There were only few results in the literature concerning complex-valued entities for discrete optimization, because they are substantially more challenging. In this paper, we introduce a non-trivial generalization of knapsack problem with a complex-valued constraint on A/C power, which casts fundamental insight to discrete optimization for smart grid. We provide results of approximability (the existence of a (1/2- e-approximation algorithm) and inapproximability (the absence of FPTAS unless P = NP) for a class of complex-valued knapsack problem, considering complex-valued A/C power with non-negative real and imaginary parts. Further, we achieve truthfulness in this setting. We also apply our results to a setting of A/C power with moderate negative imaginary part.