Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:How Unsplittable-Flow-Covering helps Scheduling with Job-Dependent Cost Functions
Speaker:Andreas Wiese
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 25 September 2014
Duration:30 Minutes
Building:E1 4
Please note: New Room!
Generalizing many well-known and natural scheduling problems, scheduling with job-specific cost functions has gained a lot of attention recently. In this setting, each job incurs a cost depending on its completion time, given by a private cost function, and one seeks to schedule the jobs to minimize the total sum of these costs. The framework captures many important scheduling objectives such as weighted flow time or weighted tardiness. Still, the general case as well as the mentioned special cases are far from being very well understood yet, even for only one machine. Aiming for better general understanding of this problem, we focus on the case of uniform job release dates on one machine for which the state of the art is a 4-approximation algorithm. This is true even for a special case that is equivalent to the covering version of the well-studied and prominent unsplittable flow on a path problem, which is interesting in its own right. For that covering problem, we present a quasi-polynomial time (1+epsilon)-approximation algorithm that yields an (e+epsilon)-approximation for the above scheduling problem.

Moreover, for the latter we devise the best possible resource augmentation result regarding speed: a polynomial time algorithm which computes a solution with optimal cost at 1+epsilon speedup. Finally, we present an elegant QPTAS for the special case where the cost functions of the jobs fall into at most log(n) many classes. This algorithm allows the jobs even to have up to log(n) many distinct release dates. All proposed quasi-polynomial time algorithms require the input data to be quasi-polynomially bounded.

Name(s):Andreas Wiese
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Andreas Wiese, 09/23/2014 03:36 PM
  • Andreas Wiese, 09/23/2014 03:35 PM -- Created document.