The $p$-Center Problem in Tree Networks Revisited

Aritra Banik, Binay K. Bhattacharya, Sandip Das, Tsunehiko Kameda, Zhao Song

This paper, "The $p$-Center Problem in Tree Networks Revisited," breaks a nearly 30-year stalemate in computational geometry. The authors present two new algorithms for the weighted discrete $p$-center problem on tree networks, outperforming the long-standing benchmark set in the mid-1980s.

TL;DR

The authors provide the first major improvement in three decades for finding the optimal locations for $p$ facilities in a tree-shaped network. By combining spine tree decomposition with fractional cascading and parametric search, they achieve a complexity of $O(n \log n + p \log^2 n \log(n/p))$, surpassing the classic $O(n \log^2 n)$ limit.

What Problem Does This Paper Address?

The $p$-center problem is a classic facility location challenge: given a network, where should you place $p$ facilities (like fire stations or warehouses) to minimize the maximum travel cost to any user? In the "weighted discrete" version (WDpC) studied here, users (vertices) have different weights representing their importance or demand, and facilities can be placed anywhere on the edges.

While the problem is NP-hard for general graphs, tree networks allow for polynomial-time solutions. However, progress for arbitrary values of $p$ had stalled since Megiddo and Tamir’s work in 1983. The challenge lies in the weighted nature of the problem, which makes simple greedy approaches for unweighted trees fail.

Methods

The authors utilize a two-part approach based on Megiddo’s parametric search framework:

  1. Feasibility Testing (The "Lower Part"): Given a cost $\alpha$, can we cover the entire tree with $p$ centers? The authors developed a root-centric location policy that places centers as close to the root as possible. To speed this up, they use fractional cascading to query "upper envelopes"—piecewise linear functions representing the maximum weighted distance from a point to vertices in a subtree.
  2. Optimization (The "Upper Part"): This part searches for the smallest feasible $\alpha^*$. For general (unbalanced) trees, they employ spine tree decomposition. This technique decomposes a tree into a set of paths (spines) such that any path from a leaf to the root in the resulting decomposition tree has only $O(\log n)$ nodes.

![Fig.

  1. Search tree for spine decomposition.](/figures/art_fcb4be3e383640929ec6ccfbae2345d6)

To handle the comparisons needed during parametric search, they utilize AKS-like sorting networks, which allow them to process multiple feasibility tests in parallel (conceptually), significantly reducing the total time spent on the search.

Datasets

Not discussed in the paper. This is a theoretical work focused on algorithmic complexity analysis rather than empirical benchmarking on specific datasets.

Key Insights and Ideas

  • Root-Centric Policy: The authors prove that if a solution exists, there is one where each center is placed at a point that covers its assigned vertices and is as close to the root as possible. This simplifies the decision-making process during the feasibility test.
  • Trimmed Trees: During the feasibility test, the algorithm identifies "peripheral centers" and then works on a "trimmed" version of the tree containing only $O(p \log n)$ vertices. This reduction is crucial for achieving the improved time complexity.
  • Handling Unbalance: Spine tree decomposition (Fig. 1) is the "secret sauce" that allows the algorithm to treat any arbitrary tree as if it were balanced, ensuring that path-based queries remain efficient.
  • Subtree Classification: The algorithm classifies subtrees as either $\oplus$-subtrees (already covered by internal centers) or $\ominus$-subtrees (requiring coverage from a center placed higher up).

![Fig.

  1. Visualizing how centers cover subtrees and how distances ($\delta$) are tracked.](/figures/art_f9aede5efb9848fcbdfc3aed87dda3b3)

Key Results

The paper introduces two primary algorithms:

  1. Theoretical Best: A complexity of $O(n \log n + p \log^2 n \log(n/p))$. This is strictly better than the previous $O(n \log^2 n)$ for all values of $p$.
  2. Practical Alternative: A complexity of $O(n \log n + p^2 \log^2(n/p))$. While theoretically slower for very large $p$, it avoids the massive constant factors associated with AKS sorting networks. It is faster than previous methods when $p = O(\sqrt{n})$.

The feasibility test itself is remarkably fast, running in $O(p \log(n/p))$ time after an $O(n \log n)$ preprocessing step.

Limitations and Future Work

The authors acknowledge that the most efficient version of their algorithm relies on AKS sorting networks. While theoretically optimal, AKS networks are notoriously difficult to implement and have very large hidden constants. However, they note that recent "AKS-like" networks with smaller constants are being discovered, which may make the theoretical algorithm more viable in the future.

Additionally, the authors suggest that their techniques could be extended to other variations of facility location problems, such as the minmax regret $p$-center problem, where they already demonstrate a sub-quadratic query time.

Summary updated

Abstract

We present two improved algorithms for weighted discrete $p$-center problem for tree networks with $n$ vertices. One of our proposed algorithms runs in $O(n \log n + p \log^2 n \log(n/p))$ time. For all values of $p$, our algorithm thus runs as fast as or faster than the most efficient $O(n\log^2 n)$ time algorithm obtained by applying Cole's speed-up technique [cole1987] to the algorithm due to Megiddo and Tamir [megiddo1983], which has remained unchallenged for nearly 30 years. Our other algorithm, which is more practical, runs in $O(n \log n + p^2 \log^2(n/p))$ time, and when $p=O(\sqrt{n})$ it is faster than Megiddo and Tamir's $O(n \log^2n \log\log n)$ time algorithm [megiddo1983].
BibTeX
@inproceedings{banik2016p,
  author = {Aritra Banik and Binay K. Bhattacharya and Sandip Das and Tsunehiko Kameda and Zhao Song},
  title = {{The $p$-Center Problem in Tree Networks Revisited}},
  booktitle = {SWAT},
  year = {2016},
  doi = {10.4230/lipics.swat.2016.6},
}
Figure