## CANCELLED: Greedy-like algorithms and a myopic model for the non-monotone submodular maximization problem

Series
ACO Seminar
Time
Monday, April 7, 2014 - 1:00pm for 1 hour (actually 50 minutes)
Location
Klaus 1116
Speaker
Allan Borodin – University of Toronto
Organizer
Robin Thomas
We are generally interested in the following ill-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 double sided 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.