Speaker: |
Mohit Garg (The Open University of Israel Derekh ha-Universita 1 Ra'anana, 4353701, Israel) |

Organiser: |
Jaikumar Radhakrishnan |

Date: |
Monday, 17 Sep 2018, 10:00 to 11:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

In a breakthrough work, Korula et al. (2015) showed that when the items arrive in a uniformly random order the greedy algorithm is at least 0.5052-competitive. Unfortunately their proof is very long and involved. In this talk we will focus on a recent work where we present an arguably much simpler analysis that provides a slightly better guarantee of 0.5096 competitiveness. Furthermore the analysis applies to a more general problem of maximizing a monotone submodular function subject to a partition constraint in the online random arrival model (previously, no algorithm was known to achieve a competitive ratio better than 1/2).

In another recent work, we study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (1/2+eps)-approximation for the problem. This algorithm is the first deterministic algorithm known to improve over the 1/2-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsey and Fisher in 1978 (joint work with Niv Buchbinder and Moran Feldman).