Serving requests that arrive on a graph as to minimize flowtime

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.