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.FSTTCS.2012.199
URN: urn:nbn:de:0030-drops-38598
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3859/
Chakaravarthy, Venkatesan T. ;
Pal, Arindam ;
Roy, Sambuddha ;
Sabharwal, Yogish
Scheduling Resources for Executing a Partial Set of Jobs
Abstract
In this paper, we consider the problem of choosing a minimum cost set of resources for executing a specified set of jobs. Each input job is an interval, determined by its start-time and end-time. Each resource is also an interval determined by its start-time and end-time; moreover, every resource has a capacity and a cost associated with it. We consider two versions of this problem.
In the partial covering version, we are also given as input a number k, specifying the number of jobs that must be performed. The goal is to choose $k$ jobs and find a minimum cost set of resources to perform the chosen k jobs (at any point of time the capacity of the chosen set of resources should be sufficient to execute the jobs active at that time). We present an O(log n)-factor approximation algorithm for this problem.
We also consider the prize collecting version, wherein every job also has a penalty associated with it. The feasible solution consists of a subset of the jobs, and a set of resources, to perform the chosen subset of jobs. The goal is to find a feasible solution that minimizes the sum of the costs of the selected resources and the penalties of the jobs that are not selected. We present a constant factor approximation algorithm for this problem.
BibTeX - Entry
@InProceedings{chakaravarthy_et_al:LIPIcs:2012:3859,
author = {Venkatesan T. Chakaravarthy and Arindam Pal and Sambuddha Roy and Yogish Sabharwal},
title = {{Scheduling Resources for Executing a Partial Set of Jobs}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
pages = {199--210},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-47-7},
ISSN = {1868-8969},
year = {2012},
volume = {18},
editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2012/3859},
URN = {urn:nbn:de:0030-drops-38598},
doi = {10.4230/LIPIcs.FSTTCS.2012.199},
annote = {Keywords: Approximation Algorithms, Partial Covering, Interval Graphs}
}
|
Keywords: |
|
Approximation Algorithms, Partial Covering, Interval Graphs |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) |
|
Issue Date: |
|
2012 |
|
Date of publication: |
|
14.12.2012 |
