Scheduling Resources for Executing a Partial Set of Jobs

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



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2012.199.pdf
  • Filesize: 0.51 MB
  • 12 pages

Document Identifiers

Author Details

Venkatesan T. Chakaravarthy
Arindam Pal
Sambuddha Roy
Yogish Sabharwal

Cite AsGet BibTex

Venkatesan T. Chakaravarthy, Arindam Pal, Sambuddha Roy, and Yogish Sabharwal. Scheduling Resources for Executing a Partial Set of Jobs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 199-210, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.FSTTCS.2012.199

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.
Keywords
  • Approximation Algorithms
  • Partial Covering
  • Interval Graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail