Original title: Analysis of the Harmonic algorithm for three servers
Authors: Chrobak, M. ; Sgall, Jiří
Document type: Research reports
Year: 2002
Language: eng
Abstract: Harmonic is a randomized $ k $-server algorithm that, at each step, given a request point $ r $, chooses the server to be moved to $ r $ with probability inversely proportional to the distance to $ r $. In this paper we prove that harmonic is $ 6 $-cotitive for $ k = 3 $.
Keywords: k-server problem; online algorithms; random walks
Project no.: LN00A056 (CEP), IAA1019901 (CEP), GA201/01/1195 (CEP), ME 476
Funding provider: GA MŠk, GA AV ČR, GA ČR, GA MŠk

Institution: Institute of Mathematics AS ČR (web)
Document availability information: Fulltext is available at the institute of the Academy of Sciences.
Original record: http://hdl.handle.net/11104/0072213

Permalink: http://www.nusl.cz/ntk/nusl-26010


The record appears in these collections:
Research > Institutes ASCR > Institute of Mathematics
Reports > Research reports