BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
BEGIN:VEVENT
CATEGORIES:Lecture
DESCRIPTION:Online Matchings and Beyond: The Power of Water-Filling -\nMany
  modern algorithmic tasks occur in an "online" setting\, in which informati
 on is revealed sequentially over time\, and a decision-maker must make irre
 vocable decisions as the situation evolves. A classic example is the Online
  Bipartite Matching problem (OBM). With applications to matching markets\, 
 ridesharing platforms\, dating apps\, and digital advertising\, OBM and its
  variants are very well-studied\, and an optimal (1-1/e)-competitive algori
 thm is known [Karp\, Vazirani\, Vazirani '90].\n\nIn this talk\, I will int
 roduce a generalization of OBM called the Online Submodular Assignment prob
 lem.  This allows us to capture more complex assignment problems of practic
 al relevance. I will show how "submodular water-levels" can be defined to a
 dapt the water-filling algorithm to the submodular setting\, and achieve an
  optimal (1-1/e)-competitive algorithm for Online SAP as well. \n\nThe talk
  will be accessible to all undergraduates with familiarity in algorithms\, 
 and it is based on joint work with Daniel Hathcock\, Billy Jin\, Kalen Patt
 on\, and Sherry Sarkar.
DTEND:20260317T233000Z
DTSTAMP:20260416T235605Z
DTSTART:20260317T224000Z
GEO:45.480972;-122.630792
LOCATION:Eliot Hall\, 314
SEQUENCE:0
SUMMARY:Computer Science Colloquium: Mik Zlatin\, Pomona College
UID:tag:localist.com\,2008:EventInstance_51934057426915
URL:https://events.reed.edu/event/computer-science-colloquium-mik-zlatin-po
 mona-college
END:VEVENT
END:VCALENDAR