Colloquium Details
Some Applications of the Multiplicative Weights Update Method in (Semi) Infinite Discrete Optimization
Speaker: Khaled Elbassioni, Masdar Institute, Khalifa University of Science and Technology
Location: Warren Weaver Hall 1302
Date: December 12, 2018, 10:30 a.m.
Host: Subhash Khot
Synopsis:
Standard (continuous or discrete) optimization problems typically assume that the dimension and the number of constrains in the problem are finite. In many practical situations, either one or both of these two parameters may be infinite. Examples include: (i) the art gallery problem from computational geometry, where it is required to guard the infinite set of points of an art gallery with the minimum number of cameras, and (ii) robust optimization problems, in which the coefficients of the constraints and/or the objective function are drawn from some infinite uncertainty sets, and the goal is to solve the optimization problem for the worst case choice in each uncertainty set. In this talk, we highlight some of these examples, and then describe how the well-known multiplicative weights update method can be applied to derive efficient approximation algorithms for solving this type of problems.
Speaker Bio:
Khaled Elbassioni is a professor at Masdar Institute, Khalifa University of Science and Technology. He holds a B.S. and an M.S. degrees in Computer Science from Alexandria University, Egypt, and a Ph.D. degree in Computer Science, which he obtained form Rutgers University under the supervision of Leonid Khachiyan in 2002. He held postdoctoral positions at Rutgers Center of operations research, between 2003 and 2004, and at Max Planck Institute for Informatics, Saarbruecken, Germany, between 2005 and 2006. From 2006 to 2012, he was a senior researcher at Max Planck Institute for Informatics. His main research interests are in the design and analysis of algorithms, particularly in the areas of discrete and continuous optimization, enumeration algorithms, and algorithmic game theory. He has served on the program committees of a number of international conferences and has been the guest editor for special issues of Algorithmica and the International Journal of Computational Geometry and Applications.
Notes:
In-person attendance only available to those with active NYU ID cards.