CATS-Apr-11-2014
Title
Greedy-like algorithms and a myopic model for the non-monotone submodular maximization problem
Speaker
Allan Borodin received his BSC from Rutgers University in 1963, and obtained an MSC degree in 1966 from Stevens Institute of Technology while working as a Member of the Technical Staff at Bell Laboratories. He returned full time to graduate school at Cornell in 1966 and received his PhD in 1969. He came to Canada and the University of Toronto in 1969 for a year or two but forgot to leave. He has been on the faculty of the Department of Computer Science at Toronto since 1969 and served as department chair from 1980-1985. He has held visiting positions at Cornell, ETH Zurich, Universite' de Nice, Hebrew University, Weizmann University, Technion, Tel Aviv University, University of Washington and the Institute for Advanced Study. Professor Borodin is a fellow of the Royal Society of Canada and a recipient of the 2008 CRM-Fields-PIMS Prize. He was appointed a University Professor in 2011.
Abstract
We are generally interested in the following not-well defined problem: What is a conceptually simple algorithm and what is the power and limitations of such algorithms? In particular, what is a greedy algorithm or more generally a myopic algorithm for a combinatorial optimization problem? And to be even more specific, motivated by the Buchbinder et al ``online greedy algorithm for the unconstrained non-monotone submodular maximization problem, what are (if any) the limitations of algorithms "of this genre" for the general unconstrained problem and for specific instances of the problem, such as Max-Di-Cut?
Joint work with Norman Huang