Top

Journal of Combinatorial Optimization

Published in:

28-11-2019

A new upper bound on the work function algorithm for the k-server problem

Authors: Wenming Zhang, Yongxi Cheng

Published in: Journal of Combinatorial Optimization | Issue 2/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The k-server problem was introduced by Manasse et al. (in: Proceedings of the 20th annual ACM symposium on theory of computing, Chicago, Illinois, USA, pp 322–333, 1988), and is one of the most famous and well-studied online problems. Koutsoupias and Papadimitriou (J ACM 42(5):971–983, 1995) showed that the work function algorithm (WFA) has a competitive ratio of at most \(2k-1\) for the k-server problem. In this paper, by proposing a potential function that is different from the one in Koutsoupias and Papadimitriou (1995), we show that the WFA has a competitive ratio of at most \(n-1\), where n is the number of points in the metric space. When \(n<2k\), this ratio is less than \(2k-1\).

previous article Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem

next article Research on the impact of green innovation alliance mode on decision-making of two-cycle closed-loop supply chain

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Bartal Y, Koutsoupias E (2004) On the competitive ratio of the work function algorithm for the \(k\)-server problem. Theor Comput Sci 324(2–3):337–345MathSciNetCrossRef

Chrobak M, Larmore LL (1992) The server problem and on-line games. In: On-line algorithms, DIMACS series in discrete mathematics and theoretical computer science, vol 7MATH

Komm D (2016) An introduction to online computation. Springer International Publishing, ChamCrossRef

Koutsoupias E (2009) The \(k\)-server problem. Comput Sci Rev 3(2):105–118CrossRef

Koutsoupias E, Papadimitriou CH (1995) On the \(k\)-server conjecture. J ACM 42(5):971–983MathSciNetCrossRef

Manasse MS, Mcgeoch LA, Sleator DD (1988) Competitive algorithms for on-line problems. In: Proceedings of the 20th annual ACM symposium on theory of computing, 2–4 May 1988, Chicago, Illinois, USA, pp 322–333

Rudec T, Manger R (2015) A fast approximate implementation of the work function algorithm for solving the \(k\)-server problem. Cent Eur J Oper Res 23(3):699–722MathSciNetCrossRef

Rudec T, Baumgartner A, Manger R (2010) Measuring true performance of the work function algorithm for solving the on-line \(k\)-server problem. J Comput Inf Technol 18(4):361–367CrossRef

Rudec T, Baumgartner A, Manger R (2013) A fast work function algorithm for solving the \(k\)-server problem. Cent Eur J Oper Res 21(1):187–205MathSciNetCrossRef

Title: A new upper bound on the work function algorithm for the k-server problem
Authors: Wenming Zhang
Yongxi Cheng
Publication date: 28-11-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 2/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00493-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2020

Equitable partition of graphs into induced linear forests

Local search strikes again: PTAS for variants of geometric covering and packing

Degree bounded bottleneck spanning trees in three dimensions

On the zero forcing number of a graph involving some classical parameters

A new leader guided optimization for the flexible job shop problem

Domination and matching in power and generalized power hypergraphs

Premium Partner