text: 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
  @cite_0: We consider the problem of allocating resources to satisfy demand requirements varying over time. The input specifies a demand for each timeslot. Each resource is specified by a start-time, end-time, an associated cost and a capacity. A feasible solution is a multiset of resources such that at any point of time, the sum of the capacities offered by the resources is at least the demand requirement at that point of time. The goal is to minimize the total cost of the resources included in the solution. This problem arises naturally in many scenarios such as workforce management, sensor networks, cloud computing, energy management and distributed computing. We study this problem under the partial cover setting and the zero-one setting. In the former scenario, the input also includes a number k and the goal is to choose a minimum cost solution that satisfies the demand requirements of at least k timeslots. For this problem, we present a 16-approximation algorithm; we show that there exist "well-structured" near-optimal solutions and that such a solution can be found in polynomial time via dynamic programming. In the zero-one setting, a feasible solution is allowed to pick at most one copy of any resource. For this case, we present a 4-approximation algorithm; our algorithm uses a novel LP relaxation involving flow-cover inequalities.
  @cite_4: In a column-restricted covering integer program (CCIP), all the non-zero entries of any column of the constraint matrix are equal. Such programs capture capacitated versions of covering problems. In this paper, we study the approximability of CCIPs, in particular, their relation to the integrality gaps of the underlying 0,1-CIP. If the underlying 0,1-CIP has an integrality gap O(γ), and assuming that the integrality gap of the priority version of the 0,1-CIP is O(ω), we give a factor O(γ+ω) approximation algorithm for the CCIP. Priority versions of 0,1-CIPs (PCIPs) naturally capture quality of service type constraints in a covering problem. We investigate priority versions of the line (PLC) and the (rooted) tree cover (PTC) problems. Apart from being natural objects to study, these problems fall in a class of fundamental geometric covering problems. We bound the integrality of certain classes of this PCIP by a constant. Algorithmically, we give a polytime exact algorithm for PLC, show that the PTC problem is APX-hard, and give a factor 2-approximation algorithm for it.
  @cite_7: We study algorithmic problems that are motivated by bandwidth trading in next-generation networks. Typically, bandwidth trading involves sellers (e.g., network operators) interested in selling bandwidth pipes that offer to buyers a guaranteed level of service for a specified time interval. The buyers (e.g., bandwidth brokers) are looking to procure bandwidth pipes to satisfy the reservation requests of end-users (e.g., Internet subscribers). Depending on what is available in the bandwidth exchange, the goal of a buyer is to either spend the least amount of money so as to satisfy all the reservations made by its customers, or to maximize its revenue from whatever reservations can be satisfied. We model this as a real-time nonpreemptive scheduling problem in which machine types correspond to bandwidth pipes and jobs correspond to end-user reservation requests. Each job specifies a time interval during which it must be processed, and a set of machine types on which it can be executed. If necessary, multiple machines of a given type may be allocated, but each must be paid for. Finally, each job has associated with it a revenue, which is realized if the job is scheduled on some machine. There are two versions of the problem that we consider. In the cost minimization version, the goal is to minimize the total cost incurred for scheduling all jobs, and in the revenue maximization version the goal is to maximize the revenue of the jobs that are scheduled for processing on a given set of machines. We consider several variants of the problems that arise in practical scenarios, and provide constant factor approximations.
  @cite_6: We present a general framework for solving resource allocation and scheduling problems. Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor. Our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines, (ii) bandwidth allocation for sessions between two endpoints, (iii) general caching, (iv) dynamic storage allocation, and (v) bandwidth allocation on optical line and ring topologies. For some of these problems we provide the first constant factor approximation algorithm. Our algorithms are simple and efficient and are based on the local-ratio technique. We note that they can equivalently be interpreted within the primal-dual schema.
summary: In the setting where resources and jobs are embodied as intervals, the objective of finding a minimum cost collection of resources that fulfill the jobs is typically called the full cover problem. Full cover problems in the interval context have been dealt with earlier, in various earlier works @cite_6 @cite_7 @cite_4 . Partial cover problems in the interval context have been considered earlier in @cite_0 . The work in existing literature that is closest in spirit to our result is that of Bar- @cite_6 , and @cite_0 . In @cite_6 , the authors consider the full cover version, and present a @math -approximation algorithm. In this case, all the jobs are to be covered, and therefore the demand profile to be covered is fixed. The goal is to find the minimum cost set of resources, for covering this profile. In our setting, we need to cover only @math of the jobs. A solution needs to select @math jobs to be covered in such a manner that the resources required to cover the resulting demand profile has minimum cost.