Motivated by the cloud computing paradigm, and by key optimization problems in all-optical networks, we study two variants of the classic job interval scheduling problem, where a reusable resource is allocated to competing job intervals in a flexible manner. Each job, @math , requires the use of up to @math units of the resource, with a profit of @math accrued for each allocated unit. The goal is to feasibly schedule a subset of the jobs so as to maximize the total profit. The resource can be allocated either in contiguous or non-contiguous blocks. These problems can be viewed as flexible variants of the well known storage allocation and bandwidth allocation problems. We show that the contiguous version is strongly NP-hard, already for instances where all jobs have the same profit and the same maximum resource requirement. For such instances, we derive the best possible positive result, namely, a polynomial time approximation scheme. We further show that the contiguous variant admits a @math -approximation algorithm, for any fixed @math , on instances whose job intervals form a proper interval graph. At the heart of the algorithm lies a non-standard parameterization of the approximation ratio itself, which is of independent interest. For the non-contiguous case, we uncover an interesting relation to the paging problem that leads to a simple @math algorithm for uniform profit instances of n jobs. The algorithm is easy to implement and is thus practical.
The classic interval scheduling problem, where each interval requires all of the resource for its execution, is solvable in @math time @cite_25 . Storage allocation problems have been studied since the 1960's (see, e.g., @cite_10 ). The traditional goal is to contiguously store a set of objects in minimum size memory. This is the well-known dynamic storage allocation ( ) problem (see, e.g., @cite_0 and the references therein). The storage allocation problem ( ) is NP-hard, since it includes Knapsack as a special case. was first studied in @cite_25 @cite_3 . Bar-Noy al @cite_25 presented an approximation algorithm that yields a ratio of @math . Chen al @cite_11 presented a polynomial time exact algorithm for the special case where all resource requirements are multiples of @math , for some fixed integer @math . Bar-Yehuda al @cite_17 presented a randomized algorithm for with ratio @math , and a deterministic algorithm with ratio @math . The best known result is a deterministic @math -approximation algorithm due to @cite_5 .
@cite_17 @cite_3 @cite_0 @cite_5 @cite_10 @cite_25 @cite_11
2096347791 1507141328 292411010 2003902046 2015840394
We study the bandwidth allocation problem (BAP) in bounded degree trees. In this problem we are given a tree and a set of connection requests. Each request consists of a path in the tree, a bandwidth requirement, and a weight. Our goal is to find a maximum weight subset S of requests such that, for every edge e, the total bandwidth of requests in S whose path contains e is at most 1. We also consider the storage allocation problem (SAP), in which it is also required that every request in the solution is given the same contiguous portion of the resource in every edge in its path. We present a deterministic approximation algorithm for BAP in bounded degree trees with ratio (2√e-1) √e-1 +epsiv;< 3.542. Our algorithm is based on a novel application of the local ratio technique in which the available bandwidth is divided into narrow strips and requests with very small bandwidths are allocated in these strips. We also present a randomized (2+e)-approximation algorithm for BAP in bounded degree trees. The best previously known ratio for BAP in general trees is 5. We present a reduction from SAP to BAP that works for instances where the tree is a line and the bandwidths are very small. It follows that there exists a (2+e)- approximation algorithm for SAP in the line. The best previously known ratio for this problem is 7. The problem we consider is motivated by allocating bandwidth slots to communication requests on a satellite channel under real time constraints. Accepted requests must be scheduled on nonintersecting rectangles in the time bandwidth Cartesian space with the goal of maximizing the benefit obtained from accepted requests. This problem turns out to be equal to the maximization version of the well known Dynamic Storage Allocation problem when storage size is limited and requests must be accommodated within a prescribed time interval. We present constant approximation algorithms for the problem introduced in this paper using as a basic step the solution of a fractional Linear Programming formulation. This problem has been independently studied by Bar- [BNBYF+00] with different techniques. Our approach gives an improved approximation ratio for the problem. We introduce two scheduling problems, the flexible bandwidth allocation problem ( ( FBAP )) and the flexible storage allocation problem ( ( FSAP )). In both problems, we have an available resource, and a set of requests, each consists of a minimum and a maximum resource requirement, for the duration of its execution, as well as a profit accrued per allocated unit of the resource. In ( FBAP ), the goal is to assign the available resource to a feasible subset of requests, such that the total profit is maximized, while in ( FSAP ) we also require that each satisfied request is given a contiguous portion of the resource. Our problems generalize the classic bandwidth allocation problem (BAP) and storage allocation problem (SAP) and are therefore ( NP-hard ). Our main results are a 3-approximation algorithm for ( FBAP ) and a ((3+ ) )-approximation algorithm for ( FSAP ), for any fixed ( >0 ). These algorithms make nonstandard use of the local ratio technique. Furthermore, we present a ((2+ ) )-approximation algorithm for ( SAP ), for any fixed ( >0 ), thus improving the best known ratio of ( 2e-1 e-1 + ). Our study is motivated also by critical resource allocation problems arising in all-optical networks. 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. We consider two allocation problems in this paper, namely, allocation of bandwidth and storage. In these problems, we face a number of independent requests, respectively, for reservation of bandwidth of a communication channel of fixed capacity and for storage of items into a space of fixed size. In both problems, a request is characterized by: (i) its required period of allocation; (ii) its required bandwidth (item width, respectively); and (iii) the profit of accepting the request. The problem is to decide which requests to accept so as to maximize the total profit. These problems in general are NP-hard. In this paper we provide polynomial-time algorithms for solving various special cases, and develop polynomial-time approximation algorithms for very general NP-hard cases with good performance guarantees.