Thumbnail
Access Restriction
Subscribed

Author Sitters, Ren A. ♦ Stougie, Leen
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2006
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword k-server problem ♦ Work function ♦ Competitive analysis ♦ Metrical service system ♦ On-line algorithms
Abstract We consider the generalized on-line two-server problem in which each server moves in its own metric space. Requests for service arrive one-by-one and every request is represented by two points: one in each metric space. The problem is to move, at every request, one of the two servers to its request-point such that the total distance travelled by the two servers is minimized.The special case in which both metric spaces are the real line is known as the CNN-problem. It has been a well-known open question in on-line optimization if an algorithm with a constant-competitive ratio exists for this problem. We answer this question in the affirmative by providing a constant-competitive algorithm for the generalized two-server problem on any metric space.The basic result in this article is a characterization of competitiveness for metrical service systems that seems much easier to use when looking for a competitive algorithm. The existence of a competitive algorithm for the generalized two-server problem follows rather easily from this result.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2006-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 53
Issue Number 3
Page Count 22
Starting Page 437
Ending Page 458


Source: ACM Digital Library