Facility Location and Clustering under Non-Uniform Constraints

21 concepts20 papers1 proposal

The Core Challenge: The Breakdown of Independence

In classic uncapacitated facility location or center-based clustering ($k$-center, $k$-median, $k$-means), the optimization problem possesses a beautiful property: locality. Once you decide which facilities to open or which cluster centers to select, assigning clients to those centers is trivial. Every client simply goes to its nearest open facility. This decoupling allows algorithms to focus entirely on the selection of centers, knowing that the assignment phase will naturally optimize itself.

However, real-world logistics, network design, and fair clustering introduce constraints that completely destroy this independence. These constraints are often non-uniform—varying from facility to facility or client to client:

  • Upper capacities: A facility can serve at most a given number of clients, and these limits vary across locations.
  • Lower bounds: A facility is economically viable only if it serves at least a minimum threshold of demand.
  • Fault tolerance and heterogeneous demands: A client requires connections to multiple distinct facilities to ensure redundancy.

When these constraints are introduced, client assignment becomes a complex combinatorial puzzle. You can no longer greedily route a client to the nearest center because that center might be full, or a distant center might desperately need more clients to meet its lower bound. This coupling introduces massive integrality gaps in standard linear programming (LP) relaxations and causes traditional local search methods to fail.

Upper Capacities and the Integrality Gap Barrier

When facilities have strict, non-uniform upper capacities, minimizing the maximum distance (as in the $k$-center problem) or the total distance (as in $k$-median) becomes significantly harder. Standard LP relaxations allow fractional assignments that look deceptively cheap but are impossible to round without violating either the capacity or the distance bounds.

To solve the capacitated $k$-center problem, algorithms must find structures that allow fractional assignments to be shifted locally without blowing up the service distance. For instance, An et al. explored the centrality of trees for the capacitated $k$-center problem to manage these assignments. Breaking a long-standing stalemate, Cygan et al. introduced a novel LP rounding technique centered on "caterpillar structures" to achieve the first constant-factor approximation for $k$-centers with non-uniform hard capacities. By organizing the fractional assignments into tree-like structures, they could systematically shift demands without violating strict capacity limits or significantly increasing travel distances.

For the non-uniform capacitated $k$-median problem, standard relaxations suffer from an unbounded integrality gap. To circumvent this, Shi Li et al. introduced a novel "configuration LP" that allows a slight violation of the facility budget (opening $(1+\epsilon)k$ facilities) to achieve a constant-factor approximation on cost, demonstrating how lifting the problem into a more structured LP space can bypass traditional hardness barriers.

The Flip Side: Lower-Bounded Facility Location

While upper capacities prevent facilities from taking too many clients, lower bounds enforce a minimum threshold of demand. The Lower-Bounded Facility Location (LBFL) problem models scenarios where a facility has high fixed operational costs and requires a minimum scale to be viable.

When these lower bounds are non-uniform, the problem becomes exceptionally difficult because the scale of demand needed to justify one facility might be orders of magnitude different from another. This heterogeneity prevents the use of standard aggregation techniques. Swamy tackled this by introducing an intermediate problem called Capacity-Discounted Uncapacitated Facility Location (CDUFL) and employing a randomized "$\alpha$-point" rounding strategy to smooth out worst-case performance. Later, Shi Li et al. provided the first constant-factor approximation for the general LBFL problem with site-specific, non-uniform lower bounds, showing how to aggregate client demands without violating the heterogeneous thresholds of open facilities.

Two-Sided Bounds, Outliers, and Heterogeneous Demands

In practical applications, constraints rarely appear in isolation. A robust clustering framework must often handle two-sided bounds (both minimum and maximum capacities) while simultaneously ignoring a small set of outliers to prevent extreme data points from distorting the solution.

Kociumaka provided the first constant-factor approximation algorithm for the capacitated $k$-center with outliers problem, showing that the intersection of these constraints can be managed despite invalidating traditional independent structural assumptions. Furthermore, Ding et al. addressed two-sided bounds and outliers simultaneously, extending LP rounding techniques to accommodate heterogeneous lower bounds across different centers. Similarly, Bajpai et al. introduced a robust algorithmic framework for the Priority $k$-Center problem with outliers, integrating budget limits and regional capacity constraints modeled by knapsacks or matroids.

Managing heterogeneous constraints also appears when clients have varying coverage or redundancy requirements rather than a uniform demand. For instance, in the Fault-Tolerant $k$-Median problem, each client has a unique requirement for multiple facility connections. Hajiaghayi et al. achieved the first constant-factor approximation for the general case of this problem. To maintain global structural integrity under these varied demands, researchers turn to dependent rounding techniques and hierarchical clustering schemes, as demonstrated by Byrka et al., ensuring that fractional decisions are coordinated rather than made independently. Similarly, Wu et al. extended these ideas to stochastic environments, combining LP relaxation with sophisticated rounding to handle capacity constraints alongside fault tolerance and stochastic uncertainty.

Bypassing Hardness via Parameterized Complexity

When non-uniform constraints make a problem completely intractable for standard polynomial-time constant approximations, a powerful alternative is to look through the lens of parameterized complexity. If the number of clusters or facilities $k$ is relatively small, we can design Fixed-Parameter Tractable (FPT) approximation algorithms whose runtimes scale exponentially with $k$ but linearly or polynomially with the number of data points $n$.

This paradigm has yielded a series of breakthroughs across different clustering objectives:

  • $k$-Center and $k$-Supplier: Goyal et al. provided tight FPT approximations for constrained versions of these problems, accommodating complex facility capacities and diversity requirements.
  • $k$-Means: Xu et al. delivered the first constant FPT approximation algorithm for hard-capacitated $k$-means, breaking the barrier imposed by non-uniform cluster capacities. Feng et al. also explored speeding up constrained $k$-means by leveraging 2-means subproblems to handle structural constraints like minimum cluster sizes or fault tolerance.
  • $k$-Median/Means Framework: Goyal et al. developed a unified FPT framework using a novel sampling technique to handle intricate constraints like $l$-diversity and chromatic clustering in general metric spaces.

Geometry and Dynamics: Expanding the Horizon

The challenge of non-uniform constraints extends into geometric and dynamic settings. In geometric spaces, standard decomposition-based approximation methods often assume infinite capacity for each facility. As noted by Pilipczuk et al., incorporating capacity constraints introduces significant combinatorial complexity that current planar partitioning and dynamic programming techniques cannot easily resolve, though they successfully developed a PTAS for the uncapacitated non-uniform facility location problem on planar graphs. In scheduling and covering domains, Bansal et al. introduced a geometric approach to handle capacitated covering problems with non-uniform capacities, reducing machine scheduling to geometric set cover.

Finally, in real-world systems, data is rarely static. Bhattacharya et al. tackled the dynamic non-uniform facility location problem in high-dimensional Euclidean spaces, highlighting that maintaining low recourse (few changes to open facilities) while respecting service limits remains a vital frontier.

By shifting from independent greedy assignments to coordinated rounding structures, configuration LPs, and FPT frameworks, researchers have systematically dismantled the barriers imposed by non-uniform constraints, turning highly coupled combinatorial nightmares into solvable optimization problems.

Key Foundational Work

Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm (2010) — contributed 1 concept elements to this direction.
Improved Approximation Guarantees for Lower-Bounded Facility Location (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_constrained_facility_location_8c9713d1,
  title = {constrained facility location},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constrained-facility-location/rdr_8c9713d1b1f6432f84963ee96cffdb03},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_constrained_facility_location_8c9713d1_v1,
  title = {constrained facility location},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constrained-facility-location/rdr_8c9713d1b1f6432f84963ee96cffdb03/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake