Metric Facility Location under Batched Random Order

Fabrizio Grandoni, Stefano Leonardi, Matteo RussoarXiv 2026 · arXiv

TL;DR

This paper introduces the batched random-order model for online metric facility location, bridging the gap between purely adversarial and purely random arrival sequences. The authors prove that the optimal competitive ratio is $\Theta(\min\{\log(B+1), \sqrt{\log(n-B+2)}\})$, revealing a surprising "hump" where intermediate numbers of batches lead to a $\sqrt{\log n}$ overhead that vanishes at the extremes.

What Problem Does This Paper Address?

In the classic Metric Facility Location (MFL) problem, an algorithm must decide whether to open expensive facilities at certain locations or connect clients to existing ones, aiming to minimize the sum of opening and connection costs. In the online version, clients arrive one by one, and decisions are irrevocable.

Historically, performance depends heavily on the arrival order:

  • Adversarial Order: The worst-case scenario, requiring a $\Theta(\log n / \log \log n)$ competitive ratio.
  • Random Order: A best-case scenario where clients are a random permutation, allowing for a constant competitive ratio.

However, real-world data often arrives in batches (e.g., all requests from one region arrive together), but the sequence of these batches might be unpredictable. This paper formalizes the batched random-order (BRO) model: an adversary partitions $n$ clients into $B$ batches, and these batches arrive in a uniformly random order. The challenge is to maintain efficiency when you see a whole batch at once but have no idea what the future batches look like.

Methods

The authors adapt the well-known Meyerson’s algorithm, which opens a facility at a new client's location with a probability proportional to the client's distance from the nearest open facility.

The "Shuffle" Strategy

A key algorithmic novelty is how they handle the batches. Even though the model reveals an entire batch at once, their algorithm independently shuffles the clients within each batch and processes them one by one. This might seem counter-intuitive—why ignore the global information of the revealed batch? The authors show that this randomized sequential processing is actually sufficient to achieve optimality.

Figure 1: The adversary fixes the clients and their batches, which are then uniformly permuted. Each batch is revealed in full, but our algorithms additionally shuffle its clients, as illustrated for batch b3.

Analysis Techniques

  • Static Keys: To analyze the random batch order, they assign a "static key" to each client based on its distance to an optimal facility and a random variable. A batch is only "expensive" (leads to a new facility opening that helps the cluster) if it contains a client with a smaller key than all previous batches.
  • Progress Bounds: They bound the number of facility openings by measuring how much each "certified" opening decreases the distance to the optimal center.
  • Non-uniform Costs: For varying facility costs, they use a "marginal" version of Meyerson’s rule, where lotteries at different price levels pay for marginal reductions in connection distance.

Datasets

This is a theoretical paper focused on algorithmic analysis and lower bounds. No empirical datasets were used for training or evaluation. The results are proven for any underlying metric space.

Key Insights and Ideas

  • The Complexity "Hump": The most striking finding is the competitive ratio's behavior. It is constant when $B=1$ (offline) and when $B=n$ (standard random order). However, for intermediate values (like $B = \sqrt{n}$), the ratio grows to $\Theta(\sqrt{\log n})$. This shows that batching actually makes the random-order problem harder.
  • Randomness within Batches Matters: Shuffling within the batch prevents the adversary from "hiding" a difficult sequence inside a single batch.
  • Tightness: The authors provide a matching lower bound using a "hidden path" construction on a binary tree. The adversary hides a path, and the algorithm must decide whether to open facilities along the path without knowing how deep it goes.
Figure 2: The lower-bound construction using a hidden path in a binary tree.

Key Results

  • Optimal Competitive Ratio: The paper establishes the tight bound of $\Theta(\min\{\log(B+1), \sqrt{\log(n-B+2)}\})$ for both uniform and non-uniform opening costs.
  • Algorithm Independence: The proposed algorithm is "robust"—it does not need to know the total number of clients ($n$) or the number of batches ($B$) in advance to achieve these bounds.
  • Lower Bound: They prove that even if the algorithm knows the entire metric space in advance, it cannot beat the $\sqrt{\log n}$ barrier for certain batch configurations.

Limitations and Future Work

  • Oblivious Adversary: The model assumes an oblivious adversary who fixes the batches before the process starts. Exploring adaptive adversaries (who choose the next batch based on the algorithm's past choices) remains an open challenge.
  • Non-Metric Spaces: The analysis relies heavily on the triangle inequality. Extending these results to non-metric facility location or general submodular costs would be a significant next step.
  • Beyond Facility Location: The "batched random order" framework could be applied to other classic online problems like Steiner Tree or $k$-server to see if similar $\sqrt{\log n}$ "humps" appear.

Summary updated

Abstract

We study online metric facility location in the batched random-order model. An adversary partitions $n$ clients into $B$ nonempty batches, which arrive in uniformly random order. Each batch is revealed in full, and its clients must be connected to open facilities before the next batch arrives. Openings and assignments are irrevocable, and the objective is to minimize the total opening and connection cost. For both uniform and nonuniform opening costs, we prove that the tight competitive ratio is \[ Θ\!\left(\min\left\{\log(B+1), \sqrt{\log(n-B+2)}\right\}\right). \] Thus, the ratio is constant both when there is a single batch and when every batch is a singleton, but intermediate numbers of batches can require a $Θ(\sqrt{\log n})$ ratio. Our algorithms build on Meyerson's algorithm (2001) and do not need to know $n$ nor $B$. A key algorithmic novelty is that we process the clients in a batch one by one in uniform random order (hence neglecting the global properties of the batch). We present a novel analysis of this algorithm that hinges on the random order of the batches, as well as of the clients within each batch. We also provide a matching competitive ratio lower bound already for uniform costs, and even when the entire metric is known in advance.
BibTeX
@misc{grandoni2026metric,
  author = {Fabrizio Grandoni and Stefano Leonardi and Matteo Russo},
  title = {{Metric Facility Location under Batched Random Order}},
  year = {2026},
  eprint = {2611.04920},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.04920},
}

Loading related content...

Figure