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
- https://www.cwi.nl/research/groups/networks-and-optimization/events/dutch-seminar-on-optimization-online-series-with-andreas-wiese-vu-amsterdam
- Dutch Seminar on Optimization (online series) with Andreas Wiese (VU Amsterdam)
- 2022-01-27T16:00:00+01:00
- 2022-01-27T17:00:00+01:00
- 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
- What English Networks & Optimization Seminars Not a Seminar
- When 27-01-2022 from 16:00 to 17:00 (Europe/Amsterdam / UTC100)
- Where Online seminar
- Contact Name Sven Polak or Daniel Dadush
- Web Visit external website
-
Add event to calendar
iCal
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.