Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Serving requests that arrive on a graph as to minimize flowtime

 
: Simroth, A.; Souza, A.

:
Volltext urn:nbn:de:0011-n-635946 (220 KByte PDF)
MD5 Fingerprint: 21773a654a107d15dbd28744db2c2d47
Erstellt am: 10.1.2008


Dresden: Fraunhofer IVI, 2007, 13 S.
Englisch
Bericht, Elektronische Publikation
Fraunhofer IVI ()
online algorithm; competitive analysis

Abstract
We study an online problem in which a server with certain speed $s$ operates on a weighted graph and has to serve requests to the vertices that arrive at some r ate. Each request takes constant time $\varepsilon > 0$ to be served and the obj ective is to minimize the total flowtime. We consider both deterministic (restri cted and unrestricted) and randomized adversaries. It turns out that the comp etitive ratio of a specific algorithm depends on the speed of the server. Even a gainst an unrestricted adversary, if the server is fast in comparison to the dia meter of the graph, then the competitive ratio is $1 + \littleO{1}$. For slow se rvers we give the lower bound $\bigOmega{\frac{h}{s}}$, where $h$ is the length of a shortest (not necessarily simple) circuit in the graph that visits all vert ices. For a restricted adversary, which is forced to "spread'' the requests in the graph, we give a bound on the competitive ratio of the algorithm that decrea ses as the diffusion grows. The bound ranges from matching the lower bound down to a constant. Furthermore we consider a randomized adversary where $0 < p \le 1 $ is a probabilistic parameter of request-diffusion. Then the competitive ratio is at most the bound against the deterministically restricted adversary up to a factor of $\bigO{p{-1}}$. Additionally we show that serving a set of known r equests can be solved optimally in polynomial time if the underlying graph is a line.

: http://publica.fraunhofer.de/dokumente/N-63594.html