2011/10/30 by René Sitters, Sitters, Rene · 1 citation
Computer Science · Decision Sciences · #68Q25 #68W27 #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1110.6600
openalex publication_date 2011/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The generalized 2-server problem is an online optimization problem where a\nsequence of requests has to be served at minimal cost. Requests arrive one by\none and need to be served instantly by at least one of two servers. We consider\nthe general model where the cost function of the two servers may be different.\nFormally, each server moves in its own metric space and a request consists of\none point in each metric space. It is served by moving one of the two servers\nto its request point. Requests have to be served without knowledge of the\nfuture requests. The objective is to minimize the total traveled distance. The\nspecial case where both servers move on the real line is known as the\nCNN-problem. We show that the generalized work function algorithm is constant\ncompetitive for the generalized 2-server problem.\n