Multi-dimensional dynamic facility location and fast computation at query points |
| |
Authors: | S. Abravaya D. Berend |
| |
Affiliation: | a Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel b Departments of Mathematics and Computer Science, Ben-Gurion University, Beer-Sheva 84105, Israel |
| |
Abstract: | We present O(nlogn) time algorithms for the minimax rectilinear facility location problem in R1 and R2. The algorithms enable, once they terminate, computing the cost of any given query point in O(logn) time. Based on these algorithms, we develop a preprocessing procedure which enables solving the following two problems: Fast computation of the cost of any query point in Rd, and fast solution for the dynamic location problem in R2 (namely, in the presence of an additional facility). Finally, we show that the preprocessing always gives a bound on the optimal value, which allows us in many cases to find the optimum fast (for both the traditional and the dynamic location problems in Rd for any d). |
| |
Keywords: | Computational geometry Minimax criterion Facility location |
本文献已被 ScienceDirect 等数据库收录! |
|