License
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://drops.dagstuhl.de/opus/volltexte/2012/3859/
Go to the corresponding LIPIcs Volume Portal


Chakaravarthy, Venkatesan T. ; Pal, Arindam ; Roy, Sambuddha ; Sabharwal, Yogish

Scheduling Resources for Executing a Partial Set of Jobs

pdf-format:
Document 1.pdf (532 KB)


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 =		{http://drops.dagstuhl.de/opus/volltexte/2012/3859},
  URN =		{urn:nbn:de:0030-drops-38598},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2012.199},
  annote =	{Keywords: Approximation Algorithms, Partial Covering, Interval Graphs}
}

Keywords: Approximation Algorithms, Partial Covering, Interval Graphs
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 10.12.2012


DROPS-Home | Fulltext Search | Imprint Published by LZI