Basser Seminar Series

A Dichotomy for the Approximability of the Complex-Demand Knapsack Problem

Speaker: Associate Professor Khaled Elbassioni
Masdar Institute

When: Wednesday 20 August 2014, 4:00-5:00pm

Where: The University of Sydney, School of IT Building, SIT Lecture Theatre (Room 123), Level 1

Add seminar to my diary

Abstract

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.

Speaker's biography

Dr. Khaled Elbassioni is an associate professor at Masdar Institute. He received B.S. and M.S. degrees in Computer Science from Alexandria University, Egypt, and a Ph.D. degree in Computer Science from Rutgers University, USA. From 2006 to 2012, he was a senior researcher at Max-Planck Institute for Informatics in Saarbruecken, Germany. His main research interests are in Theoretical Computer Science, in particular, in the complexity of enumeration problems, approximation algorithms, optimization and game theory.