Seminar: Andreas Wiese (Vrije Universiteit Amsterdam)

  • When Jan 27, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
  • Add event to calendar iCal

Speaker: Andreas Wiese (VU Amsterdam) 

Title:

A PTAS for the Unsplittable Flow on a Path problem 
(joint work with Fabrizio Grandoni and Tobias Mömke)

Zoom link: 

https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)

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. After a long sequence of improvements, the currently best known polynomial time approximation algorithm for UFP has an approximation ratio of $1+\frac{1}{e+1}+\eps < 1.269$. It has been an open question whether this problem admits a PTAS.
In this talk, we present a polynomial time $(1+\eps)$-approximation algorithm for UFP.


Video:

Slides: 
Slides