Tata Institute of Fundamental Research
New Developments in Certain Submodular Maximization Problems: Going Beyond 1/2
STCS Seminar
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)
Abstract:
Abstract: The submodular welfare maximization problem (SWM) captures an important subclass of combinatorial auctions and has been extensively studied in various settings. In this problem, there are m items and n bidders, where each bidder has a non-negative monotone submodular utility function over subsets of items, and the objective is to partition the items among the bidders in a way that maximizes the total utility of the bidders. In the online setting of SWM the items arrive one-by-one and are to be assigned to the bidders irrevocably upon arrival. The greedy algorithm, where each item on arrival is assigned to the bidder having the highest marginal utility for the item, is known to be 1/2-competitive. Kapralov et al. (2013) showed that no algorithm (even randomized) can achieve a competitive ratio better than 1/2 (unless NP=RP).
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).
| 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)
Abstract:
Abstract: The submodular welfare maximization problem (SWM) captures an important subclass of combinatorial auctions and has been extensively studied in various settings. In this problem, there are m items and n bidders, where each bidder has a non-negative monotone submodular utility function over subsets of items, and the objective is to partition the items among the bidders in a way that maximizes the total utility of the bidders. In the online setting of SWM the items arrive one-by-one and are to be assigned to the bidders irrevocably upon arrival. The greedy algorithm, where each item on arrival is assigned to the bidder having the highest marginal utility for the item, is known to be 1/2-competitive. Kapralov et al. (2013) showed that no algorithm (even randomized) can achieve a competitive ratio better than 1/2 (unless NP=RP).
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).
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).