CATS-Apr-11-2014
Title[edit]
Greedy-like algorithms and a myopic model for the non-monotone submodular maximization problem
Speaker[edit]
Vijay Vazirani got his Bachelor’s degree in Computer Science from MIT in 1979 and his Ph.D. from the University of California at Berkeley in 1983. His research career has been centered around the design of algorithms and computational complexity theory. He has made seminal contributions to the classical maximum matching problem, approximation algorithms and the computability of equilibria, particularly algorithms for computing market equilibria. His work in complexity theory includes the Valiant-Vazirani theorem, proving that if UNIQUE-SAT is in P then NP = RP.
In 2001 he published what was widely regarded as the definitive book on Approximation Algorithms. This book has been translated into Japanese, Polish, French and Chinese. He was a Distinguished SISL Visitor at the Social and Information Sciences Laboratory at Caltech during 2011-12. He is a Guggenheim Fellow and an ACM Fellow.
Abstract[edit]
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
