Seminars

View all Seminars  |  Download ICal for this event

A (2 + ϵ)-approximation algorithm for preemptive weighted flow time on a single machine

Series: Theory Seminar

Speaker: Dr. Lars Rohwedder Postdoctoral Researcher Theoretical Computer Science EPFL, Lausanne (Switzerland)

Date/Time: Sep 03 16:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I (STOC 21) managed to improve this large unspecified constant to 2+ϵ. I will give a very graphic presentation of the algorithmic techniques behind this.
<br>
<br>
Microsoft Teams Link:<br>
<a href="Link
Link
<br>
<br>
<br>
For more details about the seminar please visit the website at <a href="Link

Host Faculty: Dr. Arindam Khan