List Factoring and Relative Worst Order Analysis

Martin R. Ehmsen; Jens Svalgaard Kohrt; Kim Skak Larsen

doi:10.1007/978-3-642-18318-8_11

List Factoring and Relative Worst Order Analysis

Martin R. Ehmsen, Jens Svalgaard Kohrt, Kim Skak Larsen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

Relative worst order analysis is a supplement or alternative to competitive analysis which has been shown to give results more in accordance with observed behavior of online algorithms for a range of different online problems. The contribution of this paper is twofold. First, it adds the static list accessing problem to the collection of online problems where relative worst order analysis gives better results. Second, and maybe more interesting, it adds the non-trivial supplementary proof technique of list factoring to the theoretical toolbox for relative worst order analysis.

Original language	English
Title of host publication	Eighth Workshop on Approximation and Online Algorithms
Number of pages	12
Publisher	Springer
Publication date	2011
Pages	118-129
DOIs	https://doi.org/10.1007/978-3-642-18318-8_11
Publication status	Published - 2011

Series	Lecture Notes in Computer Science
Volume	6534

Documents & Links

10.1007/978-3-642-18318-8_11

Cite this

@inproceedings{fdf295b123aa4edf81bc5b6ef4213197,

title = "List Factoring and Relative Worst Order Analysis",

abstract = "Relative worst order analysis is a supplement or alternative to competitive analysis which has been shown to give results more in accordance with observed behavior of online algorithms for a range of different online problems. The contribution of this paper is twofold. First, it adds the static list accessing problem to the collection of online problems where relative worst order analysis gives better results. Second, and maybe more interesting, it adds the non-trivial supplementary proof technique of list factoring to the theoretical toolbox for relative worst order analysis.",

author = "Ehmsen, {Martin R.} and Kohrt, {Jens Svalgaard} and Larsen, {Kim Skak}",

year = "2011",

doi = "10.1007/978-3-642-18318-8_11",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "118--129",

booktitle = "Eighth Workshop on Approximation and Online Algorithms",

address = "Germany",

}

TY - GEN

T1 - List Factoring and Relative Worst Order Analysis

AU - Ehmsen, Martin R.

AU - Kohrt, Jens Svalgaard

AU - Larsen, Kim Skak

PY - 2011

Y1 - 2011

N2 - Relative worst order analysis is a supplement or alternative to competitive analysis which has been shown to give results more in accordance with observed behavior of online algorithms for a range of different online problems. The contribution of this paper is twofold. First, it adds the static list accessing problem to the collection of online problems where relative worst order analysis gives better results. Second, and maybe more interesting, it adds the non-trivial supplementary proof technique of list factoring to the theoretical toolbox for relative worst order analysis.

AB - Relative worst order analysis is a supplement or alternative to competitive analysis which has been shown to give results more in accordance with observed behavior of online algorithms for a range of different online problems. The contribution of this paper is twofold. First, it adds the static list accessing problem to the collection of online problems where relative worst order analysis gives better results. Second, and maybe more interesting, it adds the non-trivial supplementary proof technique of list factoring to the theoretical toolbox for relative worst order analysis.

U2 - 10.1007/978-3-642-18318-8_11

DO - 10.1007/978-3-642-18318-8_11

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 118

EP - 129

BT - Eighth Workshop on Approximation and Online Algorithms

PB - Springer

ER -