# Facility Reallocation on the Line

arXiv: https://arxiv.org/abs/2103.12894 · HTML: https://mlsanity.com/paper/2103.12894/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 35 references that are in the map.
- First posted on arXiv 23 Mar 2021.

## Builds on (most cited first, 7 of 7)

- [On Voting and Facility Location](https://mlsanity.com/paper/1512.05868/) (2015)
- [Facility Location in Evolving Metrics](https://mlsanity.com/paper/1403.6758/) (2014)
- [Dynamic Facility Location via Exponential Clocks](https://mlsanity.com/paper/1411.4476/) (2014)
- [Changing Bases: Multistage Optimization for Matroids and Matchings](https://mlsanity.com/paper/1404.3768/) (2014)
- [Local-Search based Approximation Algorithms for Mobile Facility Location Problems](https://mlsanity.com/paper/1301.4478/) (2013)
- [Reallocating Multiple Facilities on the Line](https://mlsanity.com/paper/1905.12379/) (2019)
- [Facility location with double-peaked preference](https://mlsanity.com/paper/1502.05548/) (2015)

## Built on by (most cited first, 1 of 1)

- [Efficient Online Learning for Dynamic k-Clustering](https://mlsanity.com/paper/2106.04336/) (2021)

## Abstract (arXiv)

We consider a multi-stage facility reallocation problems on the real line, where a facility is being moved between time stages based on the locations reported by n agents. The aim of the reallocation algorithm is to minimise the social cost, i.e., the sum over the total distance between the facility and all agents at all stages, plus the cost incurred for moving the facility. We study this problem both in the offline setting and online setting. In the offline case the algorithm has full knowledge of the agent locations in all future stages, and in the online setting the algorithm does not know these future locations and must decide the location of the facility on a stage-per-stage basis. We derive the optimal algorithm in both cases. For the online setting we show that its competitive ratio is (n+2)/(n+1). As neither of these algorithms turns out to yield a strategy-proof mechanism, we propose another strategy-proof mechanism which has a competitive ratio of (n+3)/(n+1) for odd n and (n+4)/n for even n, which we conjecture to be the best possible. We also consider a generalisation with multiple facilities and weighted agents, for which we show that the optimum can be computed in polynomial time for a fixed number of facilities.