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. Whe...
详细信息
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-linealgorithms 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.
The online CNN problem had no known competitive algorithms for a long time. Sitters, Stougie and de Paepe showed that there exists a competitive online algorithm for this problem. However, both their algorithm and ana...
详细信息
The online CNN problem had no known competitive algorithms for a long time. Sitters, Stougie and de Paepe showed that there exists a competitive online algorithm for this problem. However, both their algorithm and analysis are quite complicated, and above all, their upper bound for the competitive ratio is 10(5). In this paper, we examine why this problem seems so difficult. To this end we introduce a nontrivial restriction, orthogonality, against this problem and show that it decreases the competitive ratio dramatically, down to at most 9. (C) 2004 Elsevier B.V. All rights reserved.
In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that Move-To-Front (MTF) is the best list update algorithm under any s...
详细信息
In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that Move-To-Front (MTF) is the best list update algorithm under any such distribution. We also show that the performance of MTF depends on the amount of locality of reference, while the performance of any static list update algorithm is independent of the amount of locality. (C) 2012 Published by Elsevier B.V.
We consider the Work Function Algorithm for the k-server problem (Chrobak and Larmore, 1991: Koutsoupias and Papadimitriou, 1995) [2,4]. We show that if the Work Function Algorithm is c-competitive, then it is also st...
详细信息
We consider the Work Function Algorithm for the k-server problem (Chrobak and Larmore, 1991: Koutsoupias and Papadimitriou, 1995) [2,4]. We show that if the Work Function Algorithm is c-competitive, then it is also strictly (2c)-competitive. As a consequence of (Koutsoupias and Papadimitriou, 1995) [4] this also shows that the Work Function Algorithm is strictly (4k - 2)-competitive. (C) 2010 Elsevier B.V. All rights reserved.
The MIN algorithm is an offline strategy for deciding which item to replace when writing a new item to a cache. Its optimality was first established by Mattson et al. [R.L. Mattson, ***, D.R. Slutz, I.L. Traiger, Eval...
详细信息
The MIN algorithm is an offline strategy for deciding which item to replace when writing a new item to a cache. Its optimality was first established by Mattson et al. [R.L. Mattson, ***, D.R. Slutz, I.L. Traiger, Evaluation techniques for storage hierarchies, IBM Systems Journal 9 (2) (1970) 78-117] through a lengthy analysis. We provide a short and elementary proof based on a dynamic programming argument. (c) 2006 Elsevier B.V. All rights reserved.
We consider a server location problem with only one server to move. In this paper we assume that a request is given as a region and that the service can be done anywhere inside the region. Namely, for each request an ...
详细信息
We consider a server location problem with only one server to move. In this paper we assume that a request is given as a region and that the service can be done anywhere inside the region. Namely, for each request an online algorithm chooses an arbitrary point in the region and moves the server there. Note that if every request is a single point and the server must exactly go there in the given order as conventional server problems, there is no choice for the online player and the problem is trivial. Our main result shows that if the region is a regular n-gon, the competitive ratio of the greedy algorithm is 1/sin pi/2n for odd n, and 1/sin pi/n for even n. In particular for a square region, the greedy algorithm turns out to be optimal. (C) 2008 Elsevier B.V. All rights reserved.
The problem of computing spanners of unweighted graphs in streaming model is presented. The streaming model has two characteristics, firstly the input data can be accessed only sequentially in the form of a stream, an...
详细信息
The problem of computing spanners of unweighted graphs in streaming model is presented. The streaming model has two characteristics, firstly the input data can be accessed only sequentially in the form of a stream, and secondly, the working memory is smaller than the size of the entire input stream. An algorithm in this model is allowed to make one or more passes over the input stream to solve a given computational problem. Single pass and linear time streaming algorithm for computing a spanner of size O(min(m, kn1+1/k)) for any unweighted graph. Ausiello and colleagues designed such an algorithm for spanners of stretch. Another interesting open problem is to design streaming algorithm for spanners of weighted graphs. The real challenge is to design a single pass streaming algorithm for weighted graphs without affecting the optimal bound on the spanner size and constant processing time per edge.
In a FOCS 1990 paper, S. Irani proved that the First-Fit online algorithm for coloring a graph uses at most O(k log n) colors for k-inductive graphs. In this note we provide a very short proof of this fact. (C) 2008 E...
详细信息
In a FOCS 1990 paper, S. Irani proved that the First-Fit online algorithm for coloring a graph uses at most O(k log n) colors for k-inductive graphs. In this note we provide a very short proof of this fact. (C) 2008 Elsevier B.V. All rights reserved.
Sorting is a classic problem and one to which many others reduce easily. In the streaming model, however, we are allowed only one pass over the input and sublinear memory, so in general we cannot sort. In this paper w...
详细信息
Sorting is a classic problem and one to which many others reduce easily. In the streaming model, however, we are allowed only one pass over the input and sublinear memory, so in general we cannot sort. In this paper we show that, to determine the sorted order of a multiset s of size If containing sigma >= 2 distinct elements using one pass and o(n log sigma) bits of memory, it is generally necessary and sufficient that its entropy H = o(log sigma). Specifically, if S = {S-1.....S-n) and S-i1.....S-in is the stable sort of s, then we can compute i(1).....i(n) in one pass using O((H + 1)n) time and O(Hn) bits of memory, with a simple combination of classic techniques. On the other hand, in the worst case it takes that much memory to compute any sorted ordering of s in one pass. (C) 2008 Elsevier B.V. All rights reserved.
We significantly improve the previous lower bounds on the performance of randomized algorithms for on-line scheduling jobs on m identical machines. We also show that a natural idea for constructing an algorithm with m...
详细信息
We significantly improve the previous lower bounds on the performance of randomized algorithms for on-line scheduling jobs on m identical machines. We also show that a natural idea for constructing an algorithm with matching performance does not work. (C) 1997 Elsevier Science B.V.
暂无评论