Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Building Block
Online Algorithm
Point of View
Related Publications
(16)
Memory vs. randomization in online algorithms
An optimal online algorithm for metrical task systems
Amortized efficiency of list update and paging rules
On the k server conjecture
The kServer Dual and Loose Competitiveness for Paging
Subscribe
Academic
Publications
Competitive Algorithms for Server Problems
Competitive Algorithms for Server Problems,10.1016/01966774(90)90003W,Journal of Algorithms,Mark S. Manasse,Lyle A. Mcgeoch,Daniel Dominic Sleator
Edit
Competitive Algorithms for Server Problems
(
Citations: 231
)
BibTex

RIS

RefWorks
Download
Mark S. Manasse
,
Lyle A. Mcgeoch
,
Daniel Dominic Sleator
online algorithms for this problem from the competitive point of view. That is, we seek to develop online algorithms whose performance on any sequence of requests is as close as possible to the performance of the optimum offline algorithm. We obtain optimally competitive algorithms for several important cases. Because of the flexibility in choosing the distances in the graph and the number of servers, the kserver problem can be used to model a number of important paging and caching problems. It can also be used as a
building block
for solving more general problems. We show how server algorithms can be used to solve a seemingly more general class
Journal:
Journal of Algorithms  JAL
, vol. 11, no. 2, pp. 208230, 1990
DOI:
10.1016/01966774(90)90003W
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.cs.ucla.edu
)
(
www.cs.cmu.edu
)
(
www.cs.cmu.edu
)
(
linkinghub.elsevier.com
)
(
www.cs.cmu.edu
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(115)
...The kserver problem in its full generality was first posed by Manasse et al. [
16
]...
Nikhil Bansal
,
et al.
Towards the Randomized kServer Conjecture: A PrimalDual Approach
...The objective then is to place the at most k servers so as to minimize the sum of distances of demand points to their nearest servers, over some period of time [
15
]...
Matt Gibson
,
et al.
On Metric Clustering to Minimize the Sum of Radii
...The kserver problem on an nstate metric [
2
], for example, can be modeled as a metrical task system problem with � n � states 1 Another example is...
Jacob Abernethy
,
et al.
A Regularization Approach to Metrical Task Systems
...In the kserver problem [
11
] one has to decide how k mobile servers should serve a sequence of requests appearing at various locations of a metric space with altogether m locations...
...Thus with lack of practical evidence, it is not quite clear whether the competitive but complex WFA can really provide better service than much simpler but noncompetitive heuristics [6,
11
]...
...Another heuristic is the balanced algorithm (BALANCE) [
11
], which attempts to keep distances moved by various servers roughly equal, thus employing the server whose cumulative distance traveled so far plus the distance to the requested location is minimal...
...It can easily be proved [
11
] that any αcompetitive algorithm for the kserver problem must have α ≥ k. Also, it is easy to check [6] that RAND, GREEDY and BALANCE are not competitive...
...if the locations form a line [1,3], if all but two locations are covered by servers [9], or if there are exactly two servers [
11
]...
Tomislav Rudec
,
et al.
Measuring True Performance of the Work Function Algorithm for Solving ...
...ZA under the strategy A, if there exists a constant r can ensure the formula ZA(R) • rZs(R) for all the demands R, the efficiency loss of the strategy A is r, the smaller the efficiency loss r, the better the strategy A [
8
], [9]...
Xiaoping Wu
,
et al.
The Efficiency Loss of User Equilibrium with Linear Nonseparable and A...
References
(10)
Amortized efficiency of list update and paging rules
(
Citations: 1248
)
Daniel Dominic Sleator
,
Robert Endre Tarjan
Journal:
Communications of The ACM  CACM
, vol. 28, no. 2, pp. 202208, 1985
Competitive Snoopy Caching
(
Citations: 360
)
Anna R. Karlin
,
Mark S. Manasse
,
Larry Rudolph
,
Daniel Dominic Sleator
Journal:
Algorithmica
, vol. 3, no. 14, pp. 77119, 1988
Sequencing Problems in TwoServer Systems
(
Citations: 30
)
A. R. Calderbank
,
L. Flatto
Journal:
Mathematics of Operations Research  MOR
, vol. 10, no. 4, pp. 585598, 1985
Sequencing two servers on a sphere
(
Citations: 5
)
A. R. Calderbank
,
E. G. Coffman Jr
,
L. Flatto
Journal:
Stochastic Models  STOCH MODELS
, vol. 1, no. 1, pp. 1728, 1985
Algorithms for the 1server problem with excursions
(
Citations: 1
)
D. Black
,
D. D. Sleator
Published in 1987.
Sort by:
Citations
(231)
A randomized algorithm for two servers in cross polytope spaces
Wolfgang W. Bein
,
Kazuo Iwama
,
Jun Kawahara
,
Lawrence L. Larmore
,
James A. Oravec
Journal:
Theoretical Computer Science  TCS
, vol. 412, no. 7, pp. 563572, 2011
Online computation with advice
Yuval Emek
,
Pierre Fraigniaud
,
Amos Korman
,
Adi Rosén
Journal:
Theoretical Computer Science  TCS
, vol. 412, no. 24, pp. 26422656, 2011
Mass spectra of cyclic ethers formed in the lowtemperature oxidation of a series of nalkanes
Olivier Herbinet
,
Sarah Bax
,
PierreAlexandre Glaude
,
Vincent Carré
,
Frédérique BattinLeclerc
Journal:
Fuel
, vol. 90, no. 2, pp. 528535, 2011
Towards the Randomized kServer Conjecture: A PrimalDual Approach
(
Citations: 4
)
Nikhil Bansal
,
Niv Buchbinder
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 4055, 2010
On Metric Clustering to Minimize the Sum of Radii
(
Citations: 1
)
Matt Gibson
,
Gaurav Kanade
,
Erik Krohn
,
Imran A. Pirwani
,
Kasturi Varadarajan
Journal:
Algorithmica
, vol. 57, no. 3, pp. 484498, 2010