Online facility location

被引：155

作者：

Meyerson, A ^{[1
]}

机构：

[1] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA

来源：

42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2001年

关键词：

D O I：

10.1109/SFCS.2001.959917

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the online variant of facility location, in which demand points arrive one at a time and we must maintain a set of facilities to service these points. We provide a randomized online O(1)-competitive algorithm in the case where points arrive in random order. If points are ordered adversarially, we show that no algorithm can be constant-competitive, and provide an O(log n)-competitive algorithm. Our algorithms are randomized and the analysis depends heavily on the concept of expected waiting time. We also combine our techniques with those of Charikar and Guha to provide a linear-time constant approximation for the offline facility location problem.

引用

页码：426 / 431

页数：6