Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-6104
Main Title: How unsplittable-flow-covering helps scheduling with job-dependent cost functions
Author(s): Höhn, Wiebke
Mestre, Julián
Wiese, Andreas
Type: Article
Language Code: en
Abstract: 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, in this paper 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+ε)-approximation algorithm that yields an(e+ε)-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 withoptimalcost at1+εspeedup. Finally, we present an elegant QPTAS for the special case where the cost functions of the jobs fall into at mostlognmany classes. This algorithm allows the jobs even to have up tolognmany distinct release dates. All proposed quasi-polynomial time algorithms require the input data to be quasi-polynomially bounded.
URI: http://depositonce.tu-berlin.de/handle/11303/6663
http://dx.doi.org/10.14279/depositonce-6104
Issue Date: 2017
Date Available: 29-Aug-2017
DDC Class: 510 Mathematik
004 Informatik
Subject(s): approximation algorithms
scheduling
job-dependent cost functions
unsplittable flow
Creative Commons License: https://creativecommons.org/licenses/by/4.0/
Journal Title: Algorithmica
Publisher: Springer
Publisher Place: New York, NY
Publisher DOI: 10.1007/s00453-017-0300-x
EISSN: 1432-0541
ISSN: 0178-4617
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Fachgebiet Kombinatorische Optimierung und Graphenalgorithmen » Publications

Files in This Item:
File Description SizeFormat 
10.1007_s00453-017-0300-x.pdf637.12 kBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.