We consider the online problem of scheduling jobs with equal processing times on a single machine. Each job has a release time and a deadline, and the goal is to maximize the number of jobs completed by their deadline...
详细信息
We consider the online problem of scheduling jobs with equal processing times on a single machine. Each job has a release time and a deadline, and the goal is to maximize the number of jobs completed by their deadlines. Chrobak et al. (2007, SICOMP 36:6) introduce a preempt-restart model in which progress toward completing a preempted job is lost, yet that job can be restarted from scratch. They provide a 3/2-competitive deterministic algorithm and show that this is the optimal competitiveness. Their analysis is based on a complex charging scheme among individual jobs and the use of several partial functions and mappings for assigning the charges. In this paper, we provide an alternative proof of the result using a more global potential argument to compare the relative progress of the algorithm versus the optimal schedule over time. This new proof is significantly simpler and more intuitive that the original, and our technique is applicable to related problems. (C) 2008 Elsevier B.V. All rights reserved.
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.
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.
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.
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.
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 study the usefulness of lookahead in on-line server routing problems: if an on-line algorithm is not only informed about the requests released so far, but also has a limited ability to foresee future requests, what...
详细信息
We study the usefulness of lookahead in on-line server routing problems: if an on-line algorithm is not only informed about the requests released so far, but also has a limited ability to foresee future requests, what is the improvement that can be achieved in terms of the competitive ratio? We consider several on-line server routing problems in this setting, such as the on-line traveling salesman and the on-line traveling repairman problem. We show that the influence of lookahead can change considerably depending on the particular objective function and metric space considered. (C) 2008 Elsevier B.V. All rights reserved.
In [J. Csirik, G.J. Woeginger, An on-line algorithm for multidimensional bin packing, Inform. Process. Lett. 63 (1997) 171-175] the authors study the asymptotic worst case ratio between the height of the strip needed ...
详细信息
In [J. Csirik, G.J. Woeginger, An on-line algorithm for multidimensional bin packing, Inform. Process. Lett. 63 (1997) 171-175] the authors study the asymptotic worst case ratio between the height of the strip needed to on-line pack a list of boxes by means of the Harmonic Shelf Algorithm and the height of the strip used by an optimal algorithm. In this note we analyze the effectiveness of the former algorithm in terms of the ratio between the unused area inside the strip and the total size of this strip, and we show that the Harmonic Shelf Algorithm is also capable of packing items so that the asymptotic worst case value of this ratio comes arbitrarily close to 1/2. (C) 2007 Elsevier B.V. All rights reserved.
We consider the online problem k-CTP, which is the problem to guide a vehicle from some site s to some site t on a road map given by a graph G = (V, E) in which up to k (unknown) edges are blocked by avalanches. An on...
详细信息
We consider the online problem k-CTP, which is the problem to guide a vehicle from some site s to some site t on a road map given by a graph G = (V, E) in which up to k (unknown) edges are blocked by avalanches. An online algorithm learns from a blocked edge when reaching one of its endpoints. Thus, it might have to change its route to the target t up to k times. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 2k + 1 and give an easy algorithm which matches this lower bound. Furthermore, we show that randomization can not improve the competitive ratio substantially, by establishing a lower bound of k + 1 for the competitivity of randomized onlinealgorithms against an oblivious adversary. (C) 2007 Elsevier B.V. All rights reserved.
We study the online version of the Prize-Collecting Traveling Salesman Problem (PCTSP), a generalization of the Traveling Salesman Problem (TSP). In the TSP, the salesman has to visit a set of cities while minimizing ...
详细信息
We study the online version of the Prize-Collecting Traveling Salesman Problem (PCTSP), a generalization of the Traveling Salesman Problem (TSP). In the TSP, the salesman has to visit a set of cities while minimizing the length of the overall tour. In the PCTSP, each city has a given weight and penalty, and the goal is to collect a given quota of the weights of the cities while minimizing the length of the tour plus the penalties of the cities not in the tour. In the online version, cities are disclosed over time. We give a 7/3-competitive algorithm for the problem, which compares with a lower bound of 2 on the competitive ratio of any deterministic algorithm. We also show how our approach can be combined with an approximation algorithm in order to obtain an O(1)-competitive algorithm that runs in polynomial time. (C) 2008 Elsevier B.V. All rights reserved.
暂无评论