New algorithm solves facility location with 0.5% optimality gap

The paper from arXiv (July 2026) tackles the challenge of placing facilities when each demand point has its own distance-decay function—a ubiquitous yet underexploited problem. The authors first provide a structural classification: the discrete objective is always monotone submodular, guaranteeing a (1-1/e) approximation factor via greedy algorithms regardless of decay shape. They also identify that the continuous cooperative objective is concave only if the decay itself is concave; common clip-based specifications destroy concavity, making the classification tight.

On the algorithmic side, the team proposes an exact MIP for the discrete maximum-cover formulation—its LP relaxation has empirically ~0% gap, allowing branch-and-bound to solve instances with n ≤ 500 in seconds. For larger problems, they develop a force-as-gradient / large-neighborhood-search heuristic that lands within 0.5% of the discrete optimum. In extensive benchmarks with K=30, the heuristic outperformed greedy, Cooper-style alternating, particle swarm, and weighted k-means on 30/30 instances (p<10^-9). A real-world experiment on 592,667 urban delivery orders revealed that ignoring calibrated decay variation can lose up to 9.7% of captured demand and relocate facilities by up to 37% of the map. The study also calibrates retail demand decay as exponential with scale R ≈ 1.4 km.