When Is Heterogeneous Distance-Decay Facility Location Tractable? A Structural Classification, Exact Methods, and a Real-World Study

What the math gives to ML

The paper gives a useful structural rule for prototype or facility objectives: nearest-facility capture with heterogeneous decay scales reduces exactly to a weighted function of each point's nearest distance, while cooperative aggregation can preserve concavity under the right decay choice. The most transferable asset is the concavity classification: continuous cooperative objectives are concave in facility positions when the distance-decay function is concave in distance, whereas the commonly used clipped linear decay introduces a slope-increasing kink that destroys this guarantee. A practical neural adaptation is a prototype layer that trains centers and per-example or per-token distance scales with a cooperative concave relaxation, then anneals toward hard nearest-prototype assignment for sparse routing or quantization.