Time: 4:00pm Wednesday 20th August.
Location: SIT 123
Speaker: Khaled Elbassioni, Masdar Institute
Title: A dichotomy for the approximability of the complex-demand knapsack problem
Motivated by power allocation in AC (alternating current) electrical systems, we study a generalization of the classical knapsack problem, with complex-valued demands. We provide a complete dichotomy on the approximability of this problem, characterized by the maximum angle between any two demands.