Skip to yearly menu bar Skip to main content


Spotlight Poster

Dynamic Facility Location in High Dimensional Euclidean Spaces

Sayan Bhattacharya · Gramoz Goranci · Shaofeng Jiang · Yi Qian · Yubo Zhang

Hall C 4-9 #2100

Abstract: We study the facility location problem in the dynamic setting, where the goal is to efficiently process an intermixed sequence of point insertions and deletions while maintaining a high quality and stable solution. Although the problem has been studied in the context of general metrics and low-dimensional spaces, much remains unknown concerning dynamic facility location in high dimensional spaces. In this work, we present the first fully dynamic algorithm for facility location in high-dimensional spaces Rd. For any c1, our algorithm achieves O(c)-approximation, supports point updates in O~(poly(d)n1/c+o(1)) amortized time and incurs O(1) amortized recourse. More generally, our result shows that despite the linear-time lower bound on the update time for general metrics, it is possible to achieve sub-linear update times for metric spaces that admit dynamic nearest neighbour oracles. Experiments on real datasets confirm that our algorithm achieves high-quality solutions with low running time, and incurs minimal recourse.

Chat is not available.