Seminars

View all Seminars  |  Download ICal for this event

A PTAS for Unsplittable Flow on a Path

Series: Bangalore Theory Seminars

Speaker: Tobias Mömke University of Augsburg

Date/Time: May 04 16:00:00

Location: Microsoft teams - Online Talk (See Teams link below)

Abstract:
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:

Link


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