Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Scheduling Resources for Executing a Partial Set of Jobs   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

0
The categories of this paper are: hep-ph
29
The categories of this paper are: funct-an
6
The categories of this paper are: astro-ph
3
The categories of this paper are: physics
32
The categories of this paper are: atom-ph
37
The categories of this paper are: supr-con
34
The categories of this paper are: chem-ph
35
The categories of this paper are: mtrl-th
12
The categories of this paper are: nucl-th
17
The categories of this paper are: q-fin
26
The categories of this paper are: bayes-an
5
The categories of this paper are: gr-qc
18
The categories of this paper are: econ
33
The categories of this paper are: plasm-ph
2
The categories of this paper are: math
14
The categories of this paper are: math-ph