On the Additive Constant of the k-Server Work Function Algorithm

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Article , Preprint , Conference object 01 Jan 2010Embargo end date: 01 Jan 2009Publisher:Springer Berlin HeidelbergJournal:Information Processing Letters, volume 110, pages 1,120-1,123 (issn: 0020-0190,

Copyright policy )

Authors: Yuval Emek; Pierre Fraigniaud; Amos Korman; Adi Rosén;

doi: 10.1007/978-3-642-12450-1_12 , 10.1016/j.ipl.2010.09.003 , 10.48550/arxiv.0902.1378

arXiv: 0902.1378

On the Additive Constant of the k-Server Work Function Algorithm

- Summary
- Subjects
- Related research
  (2)
- Metrics

Abstract

We consider the Work Function Algorithm for the k-server problem. We show that if the Work Function Algorithm is c-competitive, then it is also strictly (2c)-competitive. As a consequence of [Koutsoupias and Papadimitriou, JACM 1995] this also shows that the Work Function Algorithm is strictly (4k-2)-competitive.

7 pages

Related Organizations

Tel Aviv University
Israel
Centre d’Economie Industrielle - CERNA
France
University of Paris
France
Paris Diderot University
France
University of Paris
France

Keywords

FOS: Computer and information sciences, online algorithms, Computer Science - Data Structures and Algorithms, Online algorithms; streaming algorithms, Data Structures and Algorithms (cs.DS), \(k\)-server problem

2 Research products, page 1 of 1

Optimal Lower Bounds for Anonymous Scheduling Mechanisms
2012IsAmongTopNSimilarDocuments
Degree Distribution of the FKP Network Model
2003IsAmongTopNSimilarDocuments

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	5
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average