Mobile facility location (extended abstract)
- 1 August 2000
- proceedings article
- Published by Association for Computing Machinery (ACM)
Abstract
In this paper we investigate the location of mobile facilities (in L∞ and L2 metric) under the motion of clients. In particular, we present lower bounds and efficient algorithms for exact and approximate maintenance of 1-center and 1-median for a set of moving points in the plane. Our algorithms are based on the kinetic framework introduced by Basch et. al [5].Keywords
This publication has 15 references indexed in Scilit:
- Locating centers in a dynamically changing network, and related problemsLocation Science, 1998
- Planar geometric location problemsAlgorithmica, 1994
- Approximation algorithms for geometric median problemsInformation Processing Letters, 1992
- Competitive algorithms for server problemsJournal of Algorithms, 1990
- On the rectangularp-center problemNaval Research Logistics (NRL), 1987
- A Best Possible Heuristic for the k-Center ProblemMathematics of Operations Research, 1985
- A simple heuristic for the p-centre problemOperations Research Letters, 1985
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related ProblemsSIAM Journal on Computing, 1983
- New Results on the Complexity of p-Centre ProblemsSIAM Journal on Computing, 1983
- A note on Fermat's problemMathematical Programming, 1973