- 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.