Optimal Time-Critical Scheduling via Resource Augmentation

We consider two fundamental problems in dynamic scheduling: scheduling to meet deadlines in a preemptive multiprocessor setting, and scheduling to provide good response time in a number of scheduling environments. When viewed from the perspective of traditional worst-case analysis, no good on-line algorithms exist for these problems, and for some variants no good off-line algorithms exist unless P = NP . We study these problems using a relaxed notion of competitive analysis, introduced by Kalyanasundaram and Pruhs, in which the on-line algorithm is allowed more resources than the optimal off-line algorithm to which it is compared. Using this approach, we establish that several well-known on-line algorithms, that have poor performance from an absolute worst-case perspective, are optimal for the problems in question when allowed moderately more resources. For optimization of average flow time, these are the first results of any sort, for any NP -hard version of the problem, that indicate that it might be possible to design good approximation algorithms.     

On-Line Resource Management with Application to Routing and Scheduling

We propose a framework to model on-line resource management problems based on an on-line version of positive linear programming. We consider both min cost problems and max benefit problems and propose logarithmic competitive algorithms that are optimal up to a constant factor. The proposed framework provides a general methodology that applies to a wide class of on-line problems: shop scheduling, packet routing, and in general a class of packing and assignment problems. Previously studied problems as on-line multiprocessor scheduling and on-line virtual circuit routing can also be modeled within this framework. Received December 18, 1996; revised March 2, 1997.     

Online Randomized Multiprocessor Scheduling

The use of randomization in online multiprocessor scheduling is studied. The problem of scheduling independent jobs on m machines online originates with Graham [16]. While the deterministic case of this problem has been studied extensively, little work has been done on the randomized case. For m= 2 a randomized 4/3-competitive algorithm was found by Bartal et al. A randomized algorithm for m ≥ 3 is presented. It achieves competitive ratios of 1.55665, 1.65888, 1.73376, 1.78295, and 1.81681, for m = 3, 4, 5, 6,7 , respectively. These competitive ratios are less than the best deterministic lower bound for m=3,4,5 and less than the best known deterministic competitive ratio for m = 3,4,5,6,7 . Two models of multiprocessor scheduling with rejection are studied. The first is the model of Bartal et al. Two randomized algorithms for this model are presented. The first algorithm performs well for small m , achieving competitive ratios of 3/2 , , for m=2,3,4 , respectively. The second algorithm outperforms the first for m ≥ 5 . It beats the deterministic algorithm of Bartal et al. for all m = 5 ,. . ., 1000 . It is conjectured that this is true for all m . The second model differs in that preemption is allowed. For this model, randomized algorithms are presented which outperform the best deterministic algorithm for small m . Received August 11, 1997; revised February 25, 1998.     

Optimal On-Line Algorithms to Minimize Makespan on Two Machines with Resource Augmentation

We study the problem of on-line scheduling on two uniformly related machines where the on-line algorithm has resources different from those of the off-line algorithm. We consider three versions of this problem, preemptive semi-online, non-preemptive on-line and preemptive on-line scheduling. For all these cases we design algorithms with best possible competitive ratios as functions of the machine speeds. This work was submitted as a part of the M.Sc. thesis of the second author. A preliminary version of this paper appeared in the proceedings of The First Workshop on Approximation and Online Algorithms (WAOA’03), pages 109–122.     

Scheduling to maximize participation

We study a problem of scheduling client requests to servers. Each client has a particular latency requirement at each server and may choose either to be assigned to some server in order to get serviced provided that her latency requirement is met, or not to participate in the assignment at all. From a global perspective, in order to optimize the performance of such a system, one would aim to maximize the number of clients that participate in the assignment. However, clients may behave selfishly in the sense that, each of them simply aims to participate in an assignment and get serviced by some server where her latency requirement is met with no regard to overall system performance. We model this selfish behavior as a strategic game, show how to compute pure Nash equilibria efficiently, and assess the impact of selfishness on system performance. We also show that the problem of optimizing performance is computationally hard to solve, even in a coordinated way, and present efficient approximation and online algorithms.     

Fault-Tolerant Real-Time Scheduling

We use competitive analysis to study how best to use redundancy to achieve fault-tolerance in online real-time scheduling. We show that the optimal way to use spatial redundancy depends on a complex interaction of the benefits, execution times, release times, and latest start times of the jobs. We give a randomized online algorithm whose competitive ratio is O( logΦ log Delta ( log ² n log m/ log log m)) for transient faults. Here n is the number of jobs, m is the number of processors, Φ is the ratio of the maximum value density of a job to the minimum value density of a job, and Δ is the ratio of the longest possible execution time to the shortest possible execution time. We show that this bound is close to optimal by giving an Ω(( log ΔΦ/ log log m) ( log m log log m) ² ) lower bound on the competitive ratio of any randomized algorithm. In the case of permanent faults, there is a randomized online algorithm that has a competitive ratio of O( log Phi log Δ (log m/log log m)). We also show a lower bound of Ω((log ΔΦ/ log log m) ( log m/log log m)) on the competitive ratio for interval scheduling with permanent faults. Received October 1997; revised January 1999.     

Competitive Optimal On-Line Leasing

Consider an on-line player who needs some equipment (e.g., a computer) for an initially unknown number of periods. At the start of each period it is determined whether the player will need the equipment during the current period and the player has two options: to pay a leasing fee c and rent the equipment for the period, or to buy it for a larger amount P . The total cost incurred by the player is the sum of all leasing fees and perhaps one purchase. The above problem, called the leasing problem (in computer science folklore it is known as the ski-rental problem), has received considerable attention in the economic literature. Using the competitive ratio as a performance measure this paper is concerned with determining the optimal competitive on-line policy for the leasing problem. For the simplest version of the leasing problem (as described above) it is known and readily derived that the optimal deterministic competitive performance is achieved by leasing for the first k-1 times and then buying, where k = P/c . This strategy pays at most 2-1/k times the optimal off-line cost. When considering alternative financial transactions one must consider their net present value. Thus, accounting for the interest rate is an essential feature of any reasonable financial model. In this paper we determine both deterministic and randomized optimal on-line leasing strategies while accounting for the interest rate factor. It is shown here, for the leasing problem, that the interest rate factor reduces the uncertainty involved. We find that the optimal deterministic competitive ratio is 1 + (1+i)(1-1/k)(1 - k(i/1+i)) , a decreasing function of the interest i (for all reasonable values of i ). For some applications, realistic values of interest rates result in relatively low competitive ratios. By using randomization the on-line player can further boost up the performance. In particular, against an oblivious adversary the on-line player can attain a strictly smaller competitive ratio of 2 - ( (k/(k-1)) ^γ - 2 )/( (k/(k-1)) ^γ -1 ) where γ = ln ( 1 - k(1 - 1/(1+i)) ) / ln(1/(1+i)) . Here again, this competitive ratio strictly decreases with i . We also study the leasing problem against a distributional adversary called ``Nature.' This adversary chooses the probability distribution of the number of leasing periods and announces this distribution before the on-line player chooses a strategy. Although at the outset this adversary appears to be weaker than the oblivious adversary, it is shown that the optimal competitive ratio against Nature equals the optimal ratio against the oblivious adversary. Received October 8, 1997; revised February 8, 1998.     

Optimal randomized algorithm for a generalized ski-rental with interest rate

We introduce the continuously compounded interest rate into a generalized ski-rental problem with two options: either pay some rental proportionally to the usage time (the rent option), or buy the equipment and then pay some reduced rental proportionally to the usage time (the generalized buy option). Under the framework of competitive analysis, a randomized algorithm for the modified model is constructed and then is proved optimal by Yao?s Lemma, and thus the optimal competitive ratio is obtained. The result shows that the introduction of the interest rate puts off the optimal purchase date and diminishes the uncertainty involved in the decision making.     

A new measure for the study of on-line algorithms

An accepted measure for the performance of an on-line algorithm is the competitive ratio introduced by Sleator and Tarjan. This measure is well motivated and has led to the development of a mathematical theory for on-line algorithms.We investigate the behavior of this measure with respect to memory needs and benefits of lookahead and find some counterintuitive features. We present lower bounds on the size of memory devoted to recording the past. It is also observed that the competitive ratio reflects no improvement in the performance of an on-line algorithm due to any (finite) amount of lookahead.We offer an alternative measure that exhibits a different and, in some respects, more intuitive behavior. In particular, we demonstrate the use of our new measure by analyzing the tradeoff between the amortized cost of on-line algorithms for the paging problem and the amount of lookahead available to them. We also derive on-line algorithms for theK-server problem on any bounded metric space, which, relative to the new measure, are optimal among all on-line algorithms (up to a factor of 2) and are within a factor of 2K from the optimal off-line performance.     

On-Line Competitive Algorithms for Call Admission in Optical Networks

We study the on-line call admission problem in optical networks. We present a general technique that allows us to reduce the problem of call admission and wavelength selection to the call admission problem. We then give randomized algorithms with logarithmic competitive ratios for specific topologies in switchless and reconfigurable optical networks. We conclude by considering full duplex communications. Received August 16, 1997; revised May 11, 1998.     

Optimal preemptive semi-online scheduling on two uniform processors

We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1,r] (r?1) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s?1, respectively. The objective is to minimize makespan. We characterize the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm along with a matching lower bound, which also holds for randomized algorithms.     

Competitive randomized algorithms for nonuniform problems

Competitive analysis is concerned with comparing the performance of on-line algorithms with that of optimal off-line algorithms. In some cases randomization can lead to algorithms with improved performance ratios on worst-case sequences. In this paper we present new randomized on-line algorithms for snoopy caching and the spin-block problem. These algorithms achieve competitive ratios approachinge/(e–1) 1.58 against an oblivious adversary. These ratios are optimal and are a surprising improvement over the best possible ratio in the deterministic case, which is 2. We also consider the situation when the request sequences for these problems are generated according to an unknown probability distribution. In this case we show that deterministic algorithms that adapt to the observed request statistics also have competitive factors approachinge/(e–1). Finally, we obtain randomized algorithms for the 2-server problem on a class of isosceles triangles. These algorithms are optimal against an oblivious adversary and have competitive ratios that approache/(e–1). This compares with the ratio of 3/2 that can be achieved on an equilateral triangle.Supported in part by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), an NSF Science and Technology Center funded under NSF Contract STC-88-09648 and supported by the New Jersey Commission on Science and Technology.     

Preemptive Online Scheduling: Optimal Algorithms for All Speeds

Our main result is an optimal online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize makespan. The algorithm is deterministic, yet it is optimal even among all randomized algorithms. In addition, it is optimal for any fixed combination of speeds of the machines, and thus our results subsume all the previous work on various special cases. Together with a new lower bound it follows that the overall competitive ratio of this optimal algorithm is between 2.054 and e≈2.718. We also give a complete analysis of the competitive ratio for three machines. T. Ebenlendr and J. Sgall partially supported by Institutional Research Plan No. AV0Z10190503, by Inst. for Theor. Comp. Sci., Prague (project 1M0545 of MŠMT ČR), grant 201/05/0124 of GA ČR, and grant IAA1019401 of GA AV ČR. W. Jawor supported by NSF grants CCF-0208856 and OISE-0340752.     

On-Line File Caching

Abstract. Consider the following file caching problem: in response to a sequence of requests for files, where each file has a specified size and retrieval cost , maintain a cache of files of total size at most some specified k so as to minimize the total retrieval cost. Specifically, when a requested file is not in the cache, bring it into the cache and pay the retrieval cost, and remove other files from the cache so that the total size of files remaining in the cache is at most k . This problem generalizes previous paging and caching problems by allowing objects of arbitrary size and cost, both important attributes when caching files for world-wide-web browsers, servers, and proxies. We give a simple deterministic on-line algorithm that generalizes many well-known paging and weighted-caching strategies, including least-recently-used, first-in-first-out, flush-when-full, and the balance algorithm. On any request sequence, the total cost incurred by the algorithm is at most k/(k-h+1) times the minimum possible using a cache of size h ≤ k . For any algorithm satisfying the latter bound, we show it is also the case that for most choices of k , the retrieval cost is either insignificant or at most a constant (independent of k ) times the optimum. This helps explain why competitive ratios of many on-line paging algorithms have been typically observed to be constant in practice.     

LRU Is Better than FIFO

In the paging problem we have to manage a two-level memory system, in which the first level has short access time but can hold only up to k pages, while the second level is very large but slow. We use competitive analysis to study the relative performance of the two best known algorithms for paging, LRU and FIFO. Sleator and Tarjan proved that the competitive ratio of LRU and FIFO is k . In practice, however, LRU is known to perform much better than FIFO. It is believed that the superiority of LRU can be attributed to locality of reference exhibited in request sequences. In order to study this phenomenon, Borodin et al. [2] refined the competitive approach by introducing the concept of access graphs. They conjectured that the competitive ratio of LRU on each access graph is less than or equal to the competitive ratio of FIFO. We prove this conjecture in this paper. Received June 2, 1997; revised January 28, 1998.     

On the Influence of Lookahead in Competitive Paging Algorithms

We introduce a new model of lookahead for on-line paging algorithms and study several algorithms using this model. A paging algorithm is n-line with strong lookahead l if it sees the present request and a sequence of future requests that contains l pairwise distinct pages. We show that strong lookahead has practical as well as theoretical importance and improves the competitive factors of on-line paging algorithms. This is the first model of lookahead having such properties. In addition to lower bounds we present a number of deterministic and randomized on-line paging algorithms with strong lookahead which are optimal or nearly optimal. Received April 8, 1994; revised May 15, 1995.     

On Capital Investment

We deal with the problem of making capital investments in machines for manufacturing a product. Opportunities for investment occur over time, every such option consists of a capital cost for a new machine and a resulting productivity gain, i.e., a lower production cost for one unit of product. The goal is that of minimizing the total production costs and capital costs when future demand for the product being produced and investment opportunities are unknown. This can be viewed as a generalization of the ski-rental problem and related to the mortgage problem [3]. If all possible capital investments obey the rule that lower production costs require higher capital investments, then we present an algorithm with constant competitive ratio. If new opportunities may be strictly superior to previous ones (in terms of both capital cost and production cost), then we give an algorithm which is O (min{1+log C , 1+log log P , 1+log M }) competitive, where C is the ratio between the highest and the lowest capital costs, P is the ratio between the highest and the lowest production costs, and M is the number of investment opportunities. We also present a lower bound on the competitive ratio of any on-line algorithm for this case, which is Ω (min{log C , log log P / log log log P , log M / log log M }). This shows that the competitive ratio of our algorithm is tight (up to constant factors) as a function of C , and not far from the best achievable as a function of P and M . Received February 6, 1997; revised November 17, 1997.     

On-line parallel heuristics, processor scheduling and robot searching under the competitive framework

In this paper we investigate parallel searches on m concurrent rays for a point target t located at some unknown distance along one of the rays. A group of p agents or robots moving at unit speed searches for t. The search succeeds when an agent reaches the point t. Given a strategy S the competitive ratio is the ratio of the time needed by the agents to find t using S and the time needed if the location of t had been known in advance. We provide a strategy with competitive ratio of 1+2(m/p−1)(m/(m−p))^m/p and prove that this is optimal. This problem has applications in multiple heuristic searches in AI as well as robot motion planning. The case p = 1 is known in the literature as the cow path problem.     

New lower bounds for online k-server routing problems

In a k-server routing problem k?1 servers move in a metric space in order to visit specified points or carry objects from sources to destinations. In the online version requests arrive online while the servers are traveling. Two classical objective functions are to minimize the makespan, i.e., the time when the last server has completed its tour (k-Traveling Salesman Problem or k-tsp) and to minimize the sum of completion times (k-Traveling Repairman Problem or k-trp). Both problems, the k-tsp and the k-trp have been studied from a competitive analysis point of view, where the cost of an online algorithm is compared to that of an optimal offline algorithm. However, the gap between the obtained competitive ratios and the corresponding lower bounds have mostly been quite large for k>1, in particular for randomized algorithms against an oblivious adversary.We reduce a number of gaps by providing new lower bounds for randomized algorithms. The most dramatic improvement is in the lower bound for the k-Dial-a-Ride-Problem (the k-trp when objects need to be carried) from to 3 which is currently also the best lower bound for deterministic algorithms.