License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.28
URN: urn:nbn:de:0030-drops-94326
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9432/
Go to the corresponding LIPIcs Volume Portal

Wiese, Andreas

Fixed-Parameter Approximation Schemes for Weighted Flowtime

pdf-format:
LIPIcs-APPROX-RANDOM-2018-28.pdf (0.5 MB)

Abstract

Given a set of n jobs with integral release dates, processing times and weights, it is a natural and important scheduling problem to compute a schedule that minimizes the sum of the weighted flow times of the jobs. There are strong lower bounds for the possible approximation ratios. In the non-preemptive case, even on a single machine the best known result is a O(sqrt{n})-approximation which is best possible. In the preemptive case on m identical machines there is a O(log min{n/m,P})-approximation (where P denotes the maximum job size) which is also best possible.
We study the problem in the parametrized setting where our parameter k is an upper bound on the maximum (integral) processing time and weight of a job, a standard parameter for scheduling problems. We present a (1+epsilon)-approximation algorithm for the preemptive and the non-preemptive case of minimizing weighted flow time on m machines with a running time of f(k,epsilon,m)* n^{O(1)}, i.e., our combined parameters are k,epsilon, and m. Key to our results is to distinguish time intervals according to whether in the optimal solution the pending jobs have large or small total weight. Depending on this we employ dynamic programming, linear programming, greedy routines, or combinations of the latter to compute the schedule for each respective interval.

BibTeX - Entry

@InProceedings{wiese:LIPIcs:2018:9432,
  author =	{Andreas Wiese},
  title =	{{Fixed-Parameter Approximation Schemes for Weighted Flowtime}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9432},
  URN =		{urn:nbn:de:0030-drops-94326},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.28},
  annote =	{Keywords: Scheduling, fixed-parameter algorithms, approximation algorithms, approximation schemes}
}

Keywords: Scheduling, fixed-parameter algorithms, approximation algorithms, approximation schemes
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI