BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/572
DTSTAMP:20230914T125929Z
SUMMARY:Partitioning Problems\, Submodular Functions and Approximating the 
 OFDMA Capacity
DESCRIPTION:Speaker: Rahul Vaze\n\nAbstract: \nAbstract: Allocating disjoin
 t resources to multiple users so as to maximize the sum-utility is a class
 ically hard problem. Finding the FDMA capacity is one such special case\, 
 where we have to allocate disjoint frequency bins to multiple users so as 
 to maximize the sum of the data rate. Typically\, in wireless applications
 \, heuristic approaches such as convex relaxation\, KKT conditions etc\,. 
 are used to solve partitioning problem. We approach this problem via resul
 ts on greedy algorithms for sub-modular functions. The main result is to s
 how that the capacity of parallel Gaussian channels is a sub-modular funct
 ion. Following this result\, we get a $2$-approximation (which is at least
  1/2 times equal) to the optimal FDMA capacity. In addition\, exploiting t
 he sub-modularity of the underlying utilities\, we also derive a truthful 
 mechanism where no user has any incentive of misreporting its utility and 
 still guarantee a price of anarchy of at most 2.\n
URL:https://www.tcs.tifr.res.in/web/events/572
DTSTART;TZID=Asia/Kolkata:20150210T160000
DTEND;TZID=Asia/Kolkata:20150210T170000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR