How to Divide a Complex-valued Cake? Complex-demand Knapsack Problem and Combinatorial Allocation in AC Electrical Systems
Although resource allocation mechanisms have been well-studied in many systems from transportation to communication networks, the rise of the smart grid presents a new range of problems, which are a departure from these systems. One of the salient characteristics is the presence of periodic time-varying entities (e.g., power, voltage, current) in AC (alternating current) electrical systems, which are often expressed in terms of complex numbers. We consider a combinatorial optimization for utility-maximizing allocation of power in AC electrical systems, based on the well-known knapsack problem.
We provide a complete dichotomy on the approximability of this problem. More precisely, we give a PTAS for a specific case, and a bi-criteria FPTAS for the general case, and show that, unless P=NP, neither a PTAS can exist for the latter case nor any bi-criteria approximation algorithm with polynomial guarantees. We extend our results to various generalized settings, such as the mixed setting with inelastic and elastic demands, truthful mechanisms, and a networked setting.
Sid Chi-Kin Chau is an assistant professor at the Masdar Institute in Abu Dhabi, UAE, which was created in collaboration with MIT. He researches in broad areas of networking, algorithms and systems, with a particular emphasis on a wide range of applications on sustainability. Previously, he was a visiting scholar at MIT, a senior research fellow at A*STAR in Singapore, and a Croucher Foundation research fellow at University College London, and a post-doctoral research associate at University of Cambridge. He received the Ph.D. from University of Cambridge and B.Eng. from Department of Information Engineering, the Chinese University of Hong Kong.
