Dutch Seminar on Optimization (online series) with Andreas Wiese (VU Amsterdam)

Everyone is welcome to attend the online seminar by Andreas Wiese (VU Amsterdam). The title of his lecture is: A PTAS for the Unsplittable Flow on a Path problem. You will find more information on the website: https://portals.project.cwi.nl/dutch-optimization-seminar/dutch-optimization-seminar

The Dutch Seminar on Optimization is an initiative to bring together researchers from the Netherlands and beyond, with topics that are centered around Optimization in a broad sense. We would like to invite all researchers, especially also PhD students, who are working on related topics to join the events. 

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)

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.

The lecture will be given online. Please visit the website for more information and the zoom link.