BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Welfare Maximization and the Supermodular Degree
DTSTART:20140820T161500
DTEND:20140820T171500
DTSTAMP:20260408T101845Z
UID:db440fad09b132bf06db72f01ed14badcc800130036b25c91104e322
CATEGORIES:Conferences - Seminars
DESCRIPTION:Rani Izsak\, Weizmann Institute\nGiven a set of items and a co
 llection of players\, each with a nonnegative monotone valuation set funct
 ion over the items\, the welfare maximization problem requires that every 
 item be allocated to exactly one player\, and one wishes to maximize the s
 um of values obtained by the players\, as computed by applying the respect
 ive valuation function to the bundle of items allocated to the player. Thi
 s problem in its full generality is $\nP$-hard\, and moreover\, at least a
 s hard to approximate as set packing. Better approximation guarantees are 
 known for restricted classes of valuation functions. In this work we intro
 duce a new parameter\, the {\\em supermodular degree} of a valuation funct
 ion\, which is a measure for the extent to which the function exhibits sup
 ermodular behavior. We design an approximation algorithm for the welfare m
 aximization problem whose approximation guarantee is linear in the supermo
 dular degree of the underlying valuation functions.\nJoint work with Uriel
  Feige.
LOCATION:INF 211 http://plan.epfl.ch/?room=INF%20211
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR