The generalized work function algorithm is competitive for the generalized 2-server problem

Research output: Contribution to JournalArticleAcademicpeer-review

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 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, WFA?, is constant competitive for the generalized 2-server problem. Further, we give an outline for a possible extension to k ≥ 2 servers and discuss the applicability of our techniques and of the work function algorithm in general. We conclude with a discussion on several open problems in online optimization. © 2014 Society for Industrial and Applied Mathematics.
Original languageEnglish
Pages (from-to)96-125
JournalSIAM Journal on Computing
Volume43
Issue number1
DOIs
Publication statusPublished - 2014

Fingerprint

Servers
Server
Online Optimization
Metric space
Applied mathematics
Real Line
Cost functions
Cost Function
Open Problems
Optimization Problem
Minimise
Costs

Bibliographical note

http://arxiv.org/pdf/1110.6600v2.pdf

Cite this

@article{55b4ed6b6cfe42c0b367c687a92023ca,
title = "The generalized work function algorithm is competitive for the generalized 2-server problem",
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 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, WFA?, is constant competitive for the generalized 2-server problem. Further, we give an outline for a possible extension to k ≥ 2 servers and discuss the applicability of our techniques and of the work function algorithm in general. We conclude with a discussion on several open problems in online optimization. {\circledC} 2014 Society for Industrial and Applied Mathematics.",
author = "R.A. Sitters",
note = "http://arxiv.org/pdf/1110.6600v2.pdf",
year = "2014",
doi = "10.1137/120885309",
language = "English",
volume = "43",
pages = "96--125",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",

}

The generalized work function algorithm is competitive for the generalized 2-server problem. / Sitters, R.A.

In: SIAM Journal on Computing, Vol. 43, No. 1, 2014, p. 96-125.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - The generalized work function algorithm is competitive for the generalized 2-server problem

AU - Sitters, R.A.

N1 - http://arxiv.org/pdf/1110.6600v2.pdf

PY - 2014

Y1 - 2014

N2 - 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 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, WFA?, is constant competitive for the generalized 2-server problem. Further, we give an outline for a possible extension to k ≥ 2 servers and discuss the applicability of our techniques and of the work function algorithm in general. We conclude with a discussion on several open problems in online optimization. © 2014 Society for Industrial and Applied Mathematics.

AB - 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 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, WFA?, is constant competitive for the generalized 2-server problem. Further, we give an outline for a possible extension to k ≥ 2 servers and discuss the applicability of our techniques and of the work function algorithm in general. We conclude with a discussion on several open problems in online optimization. © 2014 Society for Industrial and Applied Mathematics.

U2 - 10.1137/120885309

DO - 10.1137/120885309

M3 - Article

VL - 43

SP - 96

EP - 125

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 1

ER -