Abstract
The classic online facility location problem deals with finding the optimal set of facilities in an online fashion when demand requests arrive one at a time and facilities need to be opened to service these requests. In this work, we study two variants of the online facility location problem: (1) weighted requests and (2) congestion. Both of these variants are motivated by their applications to real-life scenarios, and previously known results on online facility location cannot be directly adapted to analyze them. For weighted requests, we present an online algorithm attaining a competitive ratio of $\mathcal{O}(\log n)$ in the secretarial model and show that it is optimal. For the congestion variant, where costs grow with the number of requests served, we show that there exists an algorithm attaining a constant competitive ratio for monomial congestion costs, independent of the number of requests.
Introduction
The Online Facility Location (OFL) problem is a fundamental challenge in operations research and theoretical computer science. In the standard model, a sequence of demand points arrives over time in a metric space. For each request, an algorithm must decide whether to serve it using an existing facility (incurring a service cost equal to the distance) or to open a new facility at the request's location (incurring a fixed opening cost $f$).
While the classic version is well-understood, it often fails to capture real-world complexities. A recent paper by Chakraborty and Vaze (2023) addresses two significant gaps: weighted requests, where different users have varying levels of importance or demand volume, and congestion, where the cost of using a facility increases as it becomes more crowded.
Weighted Requests in the Secretarial Model
In the weighted variant, each request is a pair $(x, w)$, where $x$ is the location and $w$ is the weight. The cost to serve this request at facility $F$ is $w \cdot d(x, F)$. This models scenarios where a single "request" might represent a group of people or a high-priority client.
The authors demonstrate that in a purely adversarial setting, weighted requests are difficult to handle, leading to a dismal competitive ratio of $\Omega(n)$. To overcome this, they employ the secretarial model, where requests arrive in a random order. They propose the Weighted Randomized Facility Location (WRFL) algorithm. When a request $(x_i, w_i)$ arrives, it opens a new facility with probability: $$p_i = \min\left\{1, \frac{w_i \cdot d(x_i, F_i)}{f}\right\}$$ where $F_i$ is the nearest existing facility. Through a novel "Selection Process" analysis, they prove this achieves an optimal $\Theta(\log n)$ competitive ratio.
Handling Facility Congestion
The congestion model introduces a convex cost function $g(k)$ for each facility, where $k$ is the number of requests it serves. This reflects real-world scenarios like wait times at a clinic or resource depletion.
The proposed Modified Randomized Facility Location (MRFL) algorithm treats the standard RFL algorithm as a black box but introduces a capacity threshold $k^*$. Once a facility serves $k^*$ requests, it is effectively "closed" to new arrivals, and a new facility is opened at the same location to reset the congestion cost. For monomial congestion costs (e.g., $g(k) = k^2$), the authors prove a constant competitive ratio of $O\left(\frac{\log k^*}{\log \log k^*}\right)$, which is remarkably independent of the total number of requests $n$.
Theoretical Lower Bounds
To establish the optimality of their results, the authors construct lower bounds using hierarchical metric spaces. A common tool for this is a binary tree metric, where distances between nodes are defined by their level in the tree.
In these constructions, the adversary can place requests in a way that forces any online algorithm to either open many facilities or incur high service costs. The tree structure allows for a precise calculation of the minimum cost required by an offline optimal solution versus the expected cost of an online strategy, providing the $\Omega(\log n)$ bound for the weighted case.
Conclusion
This research significantly extends the utility of online facility location models. By proving that weighted requests can be handled optimally under random arrival orders and that congestion costs allow for scaling-independent performance, the authors provide robust theoretical foundations for more realistic logistics and service planning. Future work may explore more general convex congestion functions and unified models that combine both weights and congestion simultaneously.
Summary updated