BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230504T120000Z
UID:a8690babe52e42f4ff7d437b60b14916-457
DTSTAMP:19700101T120016Z
DESCRIPTION:A PTAS for Unsplittable Flow on a Path
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/457/a-ptas-for-unsplittable-flow-on-a-path/
SUMMARY:In the Unsplittable Flow on a Path problem (UFP) we are given a path with edge capacities, and a set of tasks where each task is characterized by a subpath, a demand, and a weight. The goal is to select a subset of tasks of maximum total weight such that the total demand of the selected tasks using each edge e is at most the capacity of e. The problem admits a QPTAS [Bansal, Chakrabarti, Epstein, Schieber, STOC06; Batra, Garg, Kumar, Mömke, Wiese, SODA15]. After a long sequence of improvements [Bansal, Friggstad, Khandekar, Salavatipour, SODA09; Bonsma, Schulz, Wiese, FOCS11; Anagnostopoulos, Grandoni, Leonardi, Wiese, SODA14; Grandoni, Mömke, Wiese, Zhou, STOC18], the best known polynomial time approximation algorithm for UFP has an approximation ratio of 1+1/(e+1) + ε < 1.269 [Grandoni, Mömke, Wiese, SODA22]. It has been an open question whether this problem admits a PTAS. We solve this open question and present a polynomial time (1 + ε)-approximation algorithm for UFP.



Microsoft Teams links: 

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d


We are grateful to the Kirani family for generously supporting the theory seminar series



Hosts: Rameesh Paul, Rahul Madhavan, Aditya Subramanian and Aditya Abhay Lonkar
DTSTART:20230504T120000Z
END:VEVENT
END:VCALENDAR