共查询到20条相似文献,搜索用时 46 毫秒
1.
We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.This research was partially supported by NSF Grant CCR-9009753.This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648. 相似文献
2.
Competitive Optimal On-Line Leasing 总被引:30,自引:0,他引:30
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. 相似文献
3.
On the power of randomization in on-line algorithms 总被引:5,自引:0,他引:5
Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient simulation of randomized on-line algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases.A previous version of this paper appeared in the22nd ACM STOC Conference Proceedings. Part of this research was performed while A. Borodin and A. Wigderson were visitors at the International Computer Science Institute, and while G. Tardos was a visitor at the Hebrew University. 相似文献
4.
Eric Bach Joan Boyar Leah Epstein Lene M. Favrholdt Tao Jiang Kim S. Larsen Guo-Hui Lin Rob van Stee 《Journal of Scheduling》2003,6(2):131-147
The unit price seat reservation problem is investigated. The seat reservation problem is the problem of assigning seat numbers on-line to requests for reservations in a train traveling through k stations. We are considering the version where all tickets have the same price and where requests are treated fairly, that is, a request which can be fulfilled must be granted.For fair deterministic algorithms, we provide an asymptotically matching upper bound to the existing lower bound which states that all fair algorithms for this problem are
-competitive on accommodating sequences, when there are at least three seats.Additionally, we give an asymptotic upper bound of
for fair randomized algorithms against oblivious adversaries.We also examine concrete on-line algorithms, First-Fit and Random for the special case of two seats. Tight analyses of their performance are given. 相似文献
5.
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. 相似文献
6.
We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees.
Our algorithms are deterministic and run inO(logn) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized
algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan.
Research partially supported by a National Science Foundation Graduate Fellowship and by DIMACS (Center for Discrete Mathematics
and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648.
Research at Princeton University was partially supported by the National Science Foundation, Grant No. CCR-8920505, the Office
of Naval Research, Contract No. N00014-91-J-1463, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer
Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648. 相似文献
7.
S. Albers 《Algorithmica》1997,18(3):283-305
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. 相似文献
8.
A new measure for the study of on-line algorithms 总被引:3,自引:0,他引:3
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. 相似文献
9.
For motivation purpose, imagine the followingcontinuous pattern-matching problem. Two continuous pictures, each consisting of unicolor regions, are given; one picture is called thescene and the other thepattern. The problem is to find all occurrences of the pattern in the scene.As a step toward efficient algorithmic handling of the continuous pattern-matching problem by computers, where discretized representations are involved, we consider pattern-matching problems where the pattern and the text are specified either in terms of the continuous properties, or through other exemplar digitized images—a variety of alternative specifications is considered.From the perspective of areas such as computer vision or image processing, our problem definitions identify an important gap in the fundamental theory of image formation and image processing—how to determine, even in the absence of noise, if a digitized image of a scene could contain an image of a given pattern. This is done using carefulaxiomatization.
Such a digitized-based approach may lead toward building on the theory of string-matching algorithms (in one, or higher, dimensions) for the benefit of algorithmic pattern matching in image processing.This paper is the journal version of [LV2].Partially supported by NSF Grants CCR-8908286 and CCR-9305873 and the New York State Science and Technology Foundation, Center for Advanced Technology in Telecommunications, Polytechnic University, Brooklyn, NY, USA.Partially supported by NSF Grants CCR-8906949 and CCR-9111348. 相似文献
10.
On the Competitive Ratio for Online Facility Location 总被引:2,自引:0,他引:2
Dimitris Fotakis 《Algorithmica》2008,50(1):1-57
We consider the problem of Online Facility Location, where the demand points arrive online and must be assigned irrevocably
to an open facility upon arrival. The objective is to minimize the sum of facility and assignment costs. We prove that the
competitive ratio for Online Facility Location is Θ
. On the negative side, we show that no randomized algorithm can achieve a competitive ratio better than Ω
against an oblivious adversary even if the demands lie on a line segment. On the positive side, we present a deterministic
algorithm which achieves a competitive ratio of
in every metric space.
A preliminary version of this work appeared in the Proceedings of the 30th International Colloquium on Automata, Languages
and Programming (ICALP 2003), Lecture Notes in Computer Science 2719. This work was done while the author was at the Max-Planck-Institut
für Informatik, Saarbrücken, Germany, and was partially supported by the Future and Emerging Technologies programme of the
EU under contract number IST-1999-14186 (ALCOM–FT). 相似文献
11.
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. 相似文献
12.
We study the on-line Steiner tree problem on a general metric space. We show that the greedy on-line algorithm isO(log((d/z)s))-competitive, wheres is the number of regular nodes,d is the maximum metric distance between any two revealed nodes, andz is the optimal off-line cost. Our results refine the previous known bound [9] and show that AlgorithmSB of Bartalet al. [3] for the on-line file allocation problem isO(log logN)-competitive on anN-node hypercube or butterfly network. A lower bound of (log((d/z)s)) is shown to hold.We further consider the on-line generalized Steiner problem on a general metric space. We show that a class of lazy and greedy deterministic on-line algorithms areO(k· logk)-competitive and no on-line algorithm is better than (logk)-competitive, wherek is the number of distinct nodes that appear in the request sequence.For the on-line Steiner problem on a directed graph, it is shown that no deterministic on-line algorithm is better thans-competitive and the greedy on-line algorithm iss-competitive.A preliminary version of this paper has appeared in theProceedings of the Workshop on Algorithms and Data Structures, 1993, Montréal. The first author's research was partially supported by NSF Grant CCR-9009753, whilst that of the second author was partially supported by NSF Grant DDM-8909660 and a University Fellowship from the Graduate School, Yale University. 相似文献
13.
We investigate the problem of giving seat reservations on-line. We assume that a train travels from a start station to an
end station, stopping at k stations, including the first and last. Reservations can be made for any trip going from any station to any later station.
The train has a fixed number of seats. The seat reservation system attempts to maximize income. We consider the case in which
all tickets have the same price and the case in which the price of a ticket is proportional to the length of the trip. For
both cases we prove upper and lower bounds of Θ(1/k) on the competitive ratio of any ``fair' deterministic algorithm. We also define the accommodating ratio which is similar to the competitive ratio except that the only sequences of requests allowed are sequences for which the
optimal off-line algorithm could accommodate all requests. We prove upper and lower bounds of Θ(1) on the accommodating ratio of any ``fair' deterministic algorithm, in the case in which all tickets have the same price,
but Θ(1/k) in the case in which the ticket price is proportional to the length of the trip. The most surprising of these results is
that all ``fair' algorithms are at least 1/2 -accommodating when all tickets have the same price. We prove similar results bounding the performance of any ``fair' randomized
algorithm against an adaptive on-line adversary. We also consider concrete algorithms; more specifically, First-Fit and Best-Fit.
Received February 6, 1997; revised November 6, 1997. 相似文献
14.
We study an online job scheduling problem arising in networks with aggregated links. The goal is to schedule n jobs, divided into k disjoint chains, on m identical machines, without preemption, so that the jobs within each chain complete in the order of release times and the
maximum flow time is minimized.
We present a deterministic online algorithm
with competitive ratio
, and show a matching lower bound, even for randomized algorithms. The performance bound for
we derive in the paper is, in fact, more subtle than a standard competitive ratio bound, and it shows that in overload conditions
(when many jobs are released in a short amount of time),
’s performance is close to the optimum.
We also show how to compute an offline solution efficiently for k=1, and that minimizing the maximum flow time for k,m≥2 is
-hard. As by-products of our method, we obtain two offline polynomial-time algorithms for minimizing makespan: an optimal
algorithm for k=1, and a 2-approximation algorithm for any k.
W. Jawor and M. Chrobak supported by NSF grants OISE-0340752 and CCR-0208856.
Work of C. Dürr conducted while being affiliated with the Laboratoire de Recherche en Informatique, Université Paris-Sud,
91405 Orsay. Supported by the CNRS/NSF grant 17171 and ANR Alpage. 相似文献
15.
Steve Seiden 《Journal of Scheduling》2003,6(3):309-334
We consider randomized algorithms for on-line scheduling on identical machines. For two machines, a randomized algorithm achieving a competitive ratio of
was found by Bartal et al. (1995). Seiden has presented a randomized algorithm which achieves competitive ratios of 1.55665, 1.65888, 1.73376, 1.78295, and 1.81681, for m=3,4,5,6,7, respectively (Seiden, 2000). A barely random algorithm is one which is a distribution over a constant number of deterministic strategies. The algorithms of Bartal et al. and Seiden are not barely random–in fact, these algorithms potentially make a random choice for each job scheduled. We present the first barely random on-line scheduling algorithms. In addition, our algorithms use less space and time than the previous algorithms, asymptotically. 相似文献
16.
We study several natural problems in distributed decision-making from the standpoint of competitive analysis; in these problems incomplete information is a result of the distributed nature of the problem, as opposed to the on-line mode of decision making that was heretofore prevalent in this area. In several simple situations of distributed scheduling, the competitive ratio can be computed exactly, and the different ratios can be used as a measure of the value of information and communication between decision-makers. In a more general distributed scheduling situation, we give tight upper and lower bounds on the competitive ratio achievable in the deterministic case, and give an optimal randomized algorithm with a much better competitive ratio.The research of Xiaotie Deng was supported by an NSERC grant and that of C. H. Papadimitriou was supported by an NSF grant. 相似文献
17.
We develop several quasi-polynomial-time deterministic algorithms for approximating the fraction of truth assignments that satisfy a disjunctive normal form formula. The most efficient algorithm computes for a given DNF formulaF onn variables withm clauses and > 0 an estimateY such that ¦Pr[F] –Y¦ in time which is
, for any constant. Although the algorithms themselves are deterministic, their analysis is probabilistic and uses the notion of limited independence between random variables.Research supported in part by National Science Foundation Operating Grant CCR-9016468, National Science Foundation Operating Grant CCR-9304722, United States-Israel Binational Science Foundation Grant No. 89-00312, United States-Israel Binational Science Foundation Grant No. 92-00226, and ESPRIT Basic Research Grant EC-US 030.Research partially done while visiting the International Computer Science Institute and while at Carnegie Mellon University. 相似文献
18.
We introduce and study a general, abstract game played between two players called the shepherd and the adversary. The game is played in a series of rounds using a finite set of chips which are moved about in
n
. On each round, the shepherd assigns a desired direction of movement and an importance weight to each of the chips. The adversary then moves the chips in any way that need only be weakly correlated with the desired directions assigned by the shepherd. The shepherd's goal is to cause the chips to be moved to low-loss positions, where the loss of each chip at its final position is measured by a given loss function.We present a shepherd algorithm for this game and prove an upper bound on its performance. We also prove a lower bound showing that the algorithm is essentially optimal for a large number of chips. We discuss computational methods for efficiently implementing our algorithm.We show that our general drifting-game algorithm subsumes some well studied boosting and on-line learning algorithms whose analyses follow as easy corollaries of our general result. 相似文献
19.
In this paper we study the classical problem of finding disjoint paths in
graphs. This problem has been studied by a number of authors both for specific
graphs and general classes of graphs. Whereas for specific graphs many
(almost) matching upper and lower bounds are known for the competitiveness of
on-line algorithms, not much is known about how well on-line algorithms can
perform in the general setting. The best results obtained so far use the
expansion of a network to measure the algorithms performance. We use a
different parameter called the routing number that, as we will show, allows
more precise results than the expansion. It enables us to prove tight upper and
lower bounds for deterministic on-line algorithms. The upper bound is obtained
by surprisingly simple greedy-like algorithms. Interestingly, our upper bound
on the competitive ratio is even better than the best previous approximation
ratio for off-line algorithms. Furthermore, we introduce a refined variant of
the routing number and show that this variant allows us, for some classes of
graphs, to construct on-line algorithms with a competitive ratio significantly
below the best possible upper bound that could be obtained using the routing
number or the expansion of a network only. We also show that our on-line
algorithms can be transformed into efficient algorithms for the more general
unsplittable flow problem. 相似文献
20.
Online Search with Time-Varying Price Bounds 总被引:1,自引:0,他引:1
Online search is a basic online problem. The fact that its optimal deterministic/randomized solutions are given by simple formulas (however with difficult analysis) makes the problem attractive as a target to which other practical online problems can be transformed to find optimal solutions. However, since the upper/lower bounds of prices in available models are constant, natural online problems in which these bounds vary with time do not fit in the available models.We present two new models where the bounds of prices are not constant but vary with time in certain ways. The first model, where the upper and lower bounds of (logarithmic) prices have decay speed, arises from a problem in concurrent data structures, namely to maximize the (appropriately defined) freshness of data in concurrent objects. For this model we present an optimal deterministic algorithm with competitive ratio \(\sqrt{D}\), where D is the known duration of the game, and a nearly-optimal randomized algorithm with competitive ratio \(\frac{\ln D}{1+\ln2-\frac{2}{D}}\). We also prove that the lower bound of competitive ratios of randomized algorithms is asymptotically \(\frac{\ln D}{4}\).The second model is inspired by the fact that some applications do not utilize the decay speed of the lower bound of prices in the first model. In the second model, only the upper bound decreases arbitrarily with time and the lower bound is constant. Clearly, the lower bound of competitive ratios proved for the first model holds also against the stronger adversary in the second model. For the second model, we present an optimal randomized algorithm. Our numerical experiments on the freshness problem show that this new algorithm achieves much better/smaller competitive ratios than previous algorithms do, for instance 2.25 versus 3.77 for D=128. 相似文献