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.
We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1, r] (r greater than or equal to 1) arrive one by one to be scheduled on two uniform parallel processors with speed ...
详细信息
We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1, r] (r greater than or equal to 1) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s greater than or equal to 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. (C) 2004 Elsevier B.V. All rights reserved.
In this paper we investigate the online hypergraph coloring problem. fit this online problem the algorithm receives the vertices of the hypergraph in some order v(1)..... v(n) and it must color vi by only looking at t...
详细信息
In this paper we investigate the online hypergraph coloring problem. fit this online problem the algorithm receives the vertices of the hypergraph in some order v(1)..... v(n) and it must color vi by only looking at the subhypergraph H(i) = (V(i-) E(i)) where V(i) = {v1..... v(j)} and E(i) contains the edges of the hypergraph which are subsets of V(i). We show that there exists no online hypergraph coloring algorithm with sublinear competitive ratio. Furthermore we investigate some particular classes of hypergraphs (k-uniform hypergraphs, hypergraphs with bounded matching number, projective planes), we analyse the online algorithm FF and give matching lower bounds for these classes. (C) 2008 Elsevier B.V. All rights reserved.
We present short proofs on the mistake bounds of the 1-nearest neighbor algorithm on an online prediction problem of path labels. The algorithm is one of key ingredients in the algorithm by Herbster. Lever, and Pontil...
详细信息
We present short proofs on the mistake bounds of the 1-nearest neighbor algorithm on an online prediction problem of path labels. The algorithm is one of key ingredients in the algorithm by Herbster. Lever, and Pontil for general graphs. Our proofs are combinatorial and naturally show that the algorithm works when the set of labels is not binary. (C) 2010 Elsevier B.V. All rights reserved.
It is shown that the work function algorithm for the 2-evader problem has competitive ratio m - 2 for all metric spaces with m points, This settles the k-server conjecture for metric spaces with k + 2 points.
It is shown that the work function algorithm for the 2-evader problem has competitive ratio m - 2 for all metric spaces with m points, This settles the k-server conjecture for metric spaces with k + 2 points.
In this paper, we study the advice complexity of the online bipartite matching problem and the online stable marriage problem. We show that for both problems, inverted right perpendicular log(2)(n!) inverted left perp...
详细信息
In this paper, we study the advice complexity of the online bipartite matching problem and the online stable marriage problem. We show that for both problems, inverted right perpendicular log(2)(n!) inverted left perpendicular bits of advice are necessary and sufficient for a deterministic online algorithm to be optimal, where n denotes the number of vertices in one bipartition in the former problem, and the number of men in the latter. (C) 2014 Elsevier B.V. All rights reserved.
作者：
Tan, XuehouWei, QiTokai Univ
Sch Informat Sci & Technol 4-1-1 Kitakaname Hiratsuka Kanagawa 2591292 Japan Liaoning Normal Univ
Sch Comp & Informat Technol South Liushu St 1 Dalian 116081 Peoples R China
We present an on-line strategy for a mobile robot to explore an unknown simple polygon P, so as to output a so-called watchman route such that every interior point of P is visible from at least one point along the rou...
详细信息
We present an on-line strategy for a mobile robot to explore an unknown simple polygon P, so as to output a so-called watchman route such that every interior point of P is visible from at least one point along the route. The length of robot???s route is guaranteed to be at most 7 times that of the shortest watchman route that could be computed offline. This significantly improves upon the previously known 26.5-competitive strategy and confirms a conjecture due to Hoffmann et al. (2001) [10]. Our result is mainly obtained by implementing on-line a known off-line algorithm that approximates the shortest watchman route to a factor of root 2. (C) 2022 Elsevier B.V. All rights reserved.
COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook, and Sleator (1994). They showed that for any epsilon > 0, there exist COUNTER algorithms th...
详细信息
COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook, and Sleator (1994). They showed that for any epsilon > 0, there exist COUNTER algorithms that achieve a competitive ratio of root 3 + epsilon. In this paper we use a mixture of two COUNTER algorithms to achieve a competitiveness of 12/7, which is less than root 3. Furthermore, we demonstrate that it is impossible to prove a competitive ratio smaller than 12/7 for any mixture of COUNTER algorithms using the type of potential function argument that has been used so far. We also provide new lower bounds for the competitiveness of COUNTER algorithms in the standard cost model, including a 1.625 lower bound for the variant BIT and a matching 12/7 lower bound for our algorithm. (C) 1997 Elsevier Science B.V.
We study the following multi-objective combinatorial stack-up problem from delivery industry. Given a sequence q of labeled bins and two positive integers s and p. The aim is to stack-up the bins by iteratively removi...
详细信息
We study the following multi-objective combinatorial stack-up problem from delivery industry. Given a sequence q of labeled bins and two positive integers s and p. The aim is to stack-up the bins by iteratively removing one of the first s bins of the sequence and put it to one of p stack-up places. Each of these places has to contain bins of only one label, bins of different labels have to be placed on different places. If all bins of a label are removed from q, the corresponding place becomes available for bins of another label. We analyze the worst-case performance of simple algorithms for the stack-up problem that are very interesting from a practical point of view. In particular, we show that the so-called Most-Frequently on-line algorithm is (2,2)-competitive and has optimal worst-case on-line performance. (C) 2001 Elsevier Science B.V. All rights reserved.
The paging problem is defined as follows: we are given a two-level memory system, in which one level is a fast memory, called cache, capable of holding k items, and the second level is an unbounded but slow memory. At...
详细信息
The paging problem is defined as follows: we are given a two-level memory system, in which one level is a fast memory, called cache, capable of holding k items, and the second level is an unbounded but slow memory. At each given time step, a request to an item is issued. Given a request to an item p, a miss occurs if p is not present in the fast memory. In response to a miss, we need to choose an item q in the cache and replace it by p. The choice of q needs to be made on-line, without the knowledge of future requests. The objective is to design a replacement strategy with a small number of misses. In this paper we use competitive analysis to study the performance of randomized on-line paging algorithms. Our goal is to show how the concept of work functions, used previously mostly for the analysis of deterministic algorithms, can also be applied, in a systematic fashion, to the randomized case. We present two results: we first show that the: competitive ratio of the marking algorithm is exactly 2H(k) - 1. Previously, it was known to be between H-k and 2(Hk). Then we provide a new, H-k-competitive algorithm for paging. Our algorithm, as well as its analysis, is simpler than the known algorithm by McGeoch and Sleator. Another advantage of our algorithm is that it can be implemented with complexity bounds independent of the number of past requests: O(k(2) log k) memory and O(k(2)) time per request. (C) 2000 Elsevier Science B.V. All rights reserved.
暂无评论