The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem

DOI10.1137/120885309MaRDI QIDQ5419031zbMATH OpenOpenAlexFDO

Authors René A. Sitters

Publication date 4 June 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.6600

zbMATH Keywords

\(k\)-server problemCNN problemcompetitive analysismetrical service systemonline algorithmswork function algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27) Queues and service in operations research (90B22)

Abstract: The generalized 2-server problem is an online optimization problem where a sequence of requests has to be served at minimal cost. Requests arrive one by one and need to be served instantly by at least one of two servers. We consider the general model where the cost function of the two servers may be different. Formally, each server moves in its own metric space and a request consists of one point in each metric space. It is served by moving one of the two servers to its request point. Requests have to be served without knowledge of the future requests. The objective is to minimize the total traveled distance. The special case where both servers move on the real line is known as the CNN-problem. We show that the generalized work function algorithm is constant competitive for the generalized 2-server problem.

Recommendations

• scientific article; zbMATH DE number 2038743
• scientific article; zbMATH DE number 1500547
• On the competitive ratio of the work function algorithm for the k-server problem
• The generalized two-server problem
• A new upper bound on the work function algorithm for the k-server problem
• A fast work function algorithm for solving the k-server problem
• A fast approximate implementation of the work function algorithm for solving the k-server problem
• Competitive algorithms for generalized k-server in uniform metrics
• Competitive Algorithms for Generalized k -Server in Uniform Metrics
• Randomized competitive analysis for two server problems

Cited in

(14)

• Nested convex bodies are chaseable
• Memoryless algorithms for the generalized k-server problem on uniform metrics
• Metrical service systems with multiple servers
• The generalized two-server problem
• On the additive constant of the \(k\)-server work function algorithm
• scientific article; zbMATH DE number 2038743 (Why is no real title available?)
• Better Bounds for Online Line Chasing
• A 2-competitive algorithm for online convex optimization with switching costs
• Lipschitz selectors may not yield competitive algorithms for convex body chasing
• Competitive Algorithms for Generalized k -Server in Uniform Metrics
• Deterministic 3-server on a circle and the limitation of canonical potentials
• The online min-sum set cover problem
• Towards the k-server conjecture: a unifying potential, pushing the frontier to the circle
• A decomposition approach to the weighted k-server problem

This page was built for publication: The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419031)