Monday, April 7, 2014 - 13:00
1 hour (actually 50 minutes)
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.