BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/904
DTSTAMP:20230914T125942Z
SUMMARY:New Developments in Certain Submodular Maximization Problems: Going
Beyond 1/2
DESCRIPTION:Speaker: Mohit Garg (The Open University of Israel\nDerekh ha-U
niversita 1\nRa'anana\, 4353701\, Israel)\n\nAbstract: \nAbstract: The sub
modular welfare maximization problem (SWM) captures an important subclass
of combinatorial auctions and has been extensively studied in various sett
ings. In this problem\, there are m items and n bidders\, where each bidde
r 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 settin
g 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 arriv
al is assigned to the bidder having the highest marginal utility for the i
tem\, is known to be 1/2-competitive. Kapralov et al. (2013) showed that n
o algorithm (even randomized) can achieve a competitive ratio better than
1/2 (unless NP=RP).\nIn a breakthrough work\, Korula et al. (2015) showed
that when the items arrive in a uniformly random order the greedy algorith
m is at least 0.5052-competitive. Unfortunately their proof is very long a
nd involved. In this talk we will focus on a recent work where we present
an arguably much simpler analysis that provides a slightly better guarante
e of 0.5096 competitiveness. Furthermore the analysis applies to a more ge
neral problem of maximizing a monotone submodular function subject to a pa
rtition constraint in the online random arrival model (previously\, no alg
orithm was known to achieve a competitive ratio better than 1/2).\nIn anot
her recent work\, we study the problem of maximizing a monotone submodular
function subject to a matroid constraint and present a deterministic algo
rithm that achieves (1/2+eps)-approximation for the problem. This algorith
m is the first deterministic algorithm known to improve over the 1/2-appro
ximation ratio of the classical greedy algorithm proved by Nemhauser\, Wol
sey and Fisher in 1978 (joint work with Niv Buchbinder and Moran Feldman
).\n
URL:https://www.tcs.tifr.res.in/web/events/904
DTSTART;TZID=Asia/Kolkata:20180917T100000
DTEND;TZID=Asia/Kolkata:20180917T110000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR