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.ICALP.2017.31
URN: urn:nbn:de:0030-drops-74575
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7457/
Antoniadis, Antonios ;
Hoeksma, Ruben ;
Meißner, Julie ;
Verschae, José ;
Wiese, Andreas
A QPTAS for the General Scheduling Problem with Identical Release Dates
Abstract
The General Scheduling Problem (GSP) generalizes scheduling problems with sum of cost objectives such as weighted flow time and weighted tardiness. Given a set of jobs with processing times, release dates, and job dependent cost functions, we seek to find a minimum cost preemptive schedule on a single machine. The best known algorithm for this problem and also for weighted flow time/tardiness is an O(loglog P)-approximation (where P denotes the range of the job processing times), while the best lower bound shows only strong NP-hardness. When release dates are identical there is also a gap: the problem remains strongly NP-hard and the best known approximation algorithm has a ratio of e+\epsilon (running in quasi-polynomial time). We reduce the latter gap by giving a QPTAS if the numbers in the input are quasi-polynomially bounded, ruling out the existence of an APX-hardness proof unless NP\subseteq DTIME(2^polylog(n)). Our techniques are based on the QPTAS known for the UFP-Cover problem, a particular case of GSP where we must pick a subset of intervals (jobs) on the real line with associated heights and costs. If an interval is selected, its height will help cover a given demand on any point contained within the interval. We reduce our problem to a generalization of UFP-Cover and use a sophisticated divide-and-conquer procedure with interdependent non-symmetric subproblems.
We also present a pseudo-polynomial time approximation scheme for two variants of UFP-Cover. For the case of agreeable intervals we give an algorithm based on a new dynamic programming approach which might be useful for other problems of this type. The second one is a resource augmentation setting where we are allowed to slightly enlarge each interval.
BibTeX - Entry
@InProceedings{antoniadis_et_al:LIPIcs:2017:7457,
author = {Antonios Antoniadis and Ruben Hoeksma and Julie Mei{\ss}ner and Jos{\'e} Verschae and Andreas Wiese},
title = {{A QPTAS for the General Scheduling Problem with Identical Release Dates}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {31:1--31:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7457},
URN = {urn:nbn:de:0030-drops-74575},
doi = {10.4230/LIPIcs.ICALP.2017.31},
annote = {Keywords: Generalized Scheduling, QPTAS, Unsplittable Flows}
}
|
Keywords: |
|
Generalized Scheduling, QPTAS, Unsplittable Flows |
|
Collection: |
|
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.07.2017 |
