Seminars
View all Seminars | Download ICal for this eventA 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