BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20260308T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20261101T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:6ae90084a7345
DTSTART;TZID=America/Toronto:20261102T110000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20261102T120000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read
 ing-group-rian-neogi-approximating-nash-social
SUMMARY:CombOpt Reading Group | Rian Neogi\, Approximating Nash Social Welf
 are\nvia stable polynomials
CLASS:PUBLIC
DESCRIPTION:SPEAKER:\n\nRian Neogi\n\nAFFILIATION:\n University of Waterloo
 \n\nROOM:\n MC 6029\n\nABSTRACT: In this talk\, I will go through the pap
 er of \"Nash Social\nWelfare\, Matrix Permanent\, and Stable Polynomials\"
  by Anari\, Oveis\nGharan\, Saberi\, Singh. We will consider the problem o
 f allocating m\nitems to n agents. Each agent has a value v_{ij} for item 
 j. The goal\nis to construct an allocation A_1\,...\,A_n so as to maximize
  the Nash\nsocial welfare \\prod_i \\sum_{j in A_i} v_{ij}. We will prove 
 a simple\n1/e approximation for the problem.\n\nThe techniques involve pro
 ving a generalization of the Van Der Waerden\ntheorem for bounding the per
 manent of a doubly-stochastic matrix. We\nsetup a convex program relaxatio
 n of the problem. Using the\naforementioned theorem\, we show that a simpl
 e rounding procedure on\nthe optimal solution of this program gives the 1/
 e-approximation.
DTSTAMP:20261102T212836Z
END:VEVENT
END:VCALENDAR