License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05031.29
URN: urn:nbn:de:0030-drops-684
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/68/
Go to the corresponding Portal

Schäfer, Guido ; Sivadasan, Naveen

Topology Matters: Smoothed Competitiveness of Metrical Task Systems

pdf-format:
05031.SchaeferGuido.ExtAbstract.68.pdf (0.09 MB)

Abstract

We consider online problems that can be modeled as metrical task systems: An online algorithm resides in a graph of n nodes and may move in this graph at a cost equal to the distance. The algorithm has to service a sequence of tasks that arrive over time; each task specifies for each node a request cost that is incurred if the algorithm services the task in this particular node. The objective is to minimize the total request plus travel cost. Borodin, Linial and Saks gave a deterministic work function algorithm (WFA) for metrical task systems having a tight competitive ratio of 2n-1. We present a smoothed competitive analysis of WFA. Given an adversarial task sequence, we add some random noise to the request costs and analyze the competitive ratio of WFA on the perturbed sequence. We prove upper and matching lower bounds. Our analysis reveals that the smoothed competitive ratio of WFA is much better than its (worst case) competitive ratio and that it depends on several topological parameters of the graph underlying the metric, such as maximum degree, diameter, etc. For example, already for moderate perturbations, the smoothed competitive ratio of WFA is O(log(n)) on a clique and O(\sqrt{n}) on a line. We also provide the first average case analysis of WFA. For a large class of probability distributions, we prove that WFA has O(log(D)) expected competitive ratio, where D is the maximum degree of the underlying graph.

BibTeX - Entry

@InProceedings{schafer_et_al:DagSemProc.05031.29,
  author =	{Sch\"{a}fer, Guido and Sivadasan, Naveen},
  title =	{{Topology Matters: Smoothed Competitiveness of Metrical Task Systems}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/68},
  URN =		{urn:nbn:de:0030-drops-684},
  doi =		{10.4230/DagSemProc.05031.29},
  annote =	{Keywords: online algorithm, metrical task systems, work function algorithm, smoothed competitive analysis}
}

Keywords: online algorithm, metrical task systems, work function algorithm, smoothed competitive analysis
Collection: 05031 - Algorithms for Optimization with Incomplete Information
Issue Date: 2005
Date of publication: 30.05.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI