Learning to Approximate Uniform Facility Location via Graph Neural Networks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916008235630592 |
|---|---|
| author | Qian, Chendi Morris, Christopher Jegelka, Stefanie Sohler, Christian |
| author_facet | Qian, Chendi Morris, Christopher Jegelka, Stefanie Sohler, Christian |
| contents | Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based methods rely on supervision, reinforcement learning, or gradient estimators, causing high computational cost, unstable training, or limited guarantees. Classical approximation algorithms provide worst-case guarantees but are non-differentiable and cannot adapt to structure in natural input distributions. We study this tradeoff through Uniform Facility Location (UniFL), a problem with applications in clustering, summarization, logistics, and supply chains. We propose a fully differentiable MPNN that incorporates approximation-algorithmic principles without solver supervision or discrete relaxations. The model has provable approximation guarantees and empirically improves on standard approximation algorithms, narrowing the gap to integer linear programming. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_13155 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Learning to Approximate Uniform Facility Location via Graph Neural Networks Qian, Chendi Morris, Christopher Jegelka, Stefanie Sohler, Christian Machine Learning Data Structures and Algorithms Neural and Evolutionary Computing Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based methods rely on supervision, reinforcement learning, or gradient estimators, causing high computational cost, unstable training, or limited guarantees. Classical approximation algorithms provide worst-case guarantees but are non-differentiable and cannot adapt to structure in natural input distributions. We study this tradeoff through Uniform Facility Location (UniFL), a problem with applications in clustering, summarization, logistics, and supply chains. We propose a fully differentiable MPNN that incorporates approximation-algorithmic principles without solver supervision or discrete relaxations. The model has provable approximation guarantees and empirically improves on standard approximation algorithms, narrowing the gap to integer linear programming. |
| title | Learning to Approximate Uniform Facility Location via Graph Neural Networks |
| topic | Machine Learning Data Structures and Algorithms Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2602.13155 |