Metraipolis › archive › dc_8a0aec8bb3d7
Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon — arXiv:2610.00422
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.00422
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T12:09:24.325Z
- SHA-256 of the archived text
2cf4a84d782920f3faa3d3dc01a75cc3bbdcd9a9764436662371a9e49372c22e- Stable URL of this page
https://metraipolis.com/documento/dc_8a0aec8bb3d7
How to cite
Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon — arXiv:2610.00422 — arXiv (en), https://arxiv.org/abs/2610.00422 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8a0aec8bb3d7 (Metraipolis archive dc_8a0aec8bb3d7, sha256 2cf4a84d782920f3faa3d3dc01a75cc3bbdcd9a9764436662371a9e49372c22e)
BibTeX
@misc{dc8a0aec8bb3d7,
title = {Learning to Cover Locally: Graph Neural Combinatorial Optimization under a Hard Information Horizon — arXiv:2610.00422},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.00422},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8a0aec8bb3d7; sha256 2cf4a84d782920f3faa3d3dc01a75cc3bbdcd9a9764436662371a9e49372c22e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.00422. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Neural combinatorial optimization typically assumes a centralized solver that reads the whole instance. We study the opposite: combinatorial optimization under a hard information horizon, where every node commits to its share of a global solution seeing only its $k$-hop neighborhood, and those commitments must compose into a globally feasible solution. We formalize this as local set cover and instantiate it on weighted multipoint relay (MPR) selection, the NP-hard 2-hop covering problem of the Optimized Link State Routing Protocol version 2 (OLSRv2) routing protocol (RFC~7181), whose horizon is imposed by the protocol, not chosen by the modeler. We prove two results. Any deterministic selector whose horizon is one hop short must either fail coverage or land a factor $\Delta$ from optimal, and an $L$-layer graph neural network (GNN) read out at the deciding node is exactly an $L$-hop selector, so capacity cannot buy back radius. Conversely, at the horizon a \ac{GNN} of depth $O(\Delta)$ reproduces the RFC~7181 covering greedy, and at width $O(c_{\max}\Delta)$ its metric-aware weighted analogue, inheriting the $(1+\ln\Delta_2)$-approximation in both cases. Empirically, a 3-layer \ac{GATv2} with a coverage-completing decoder, behavior-cloned from the CP-SAT optimum, reaches $\text{cost}/\text{opt}=1.030\pm0.001$ against greedy's $1.138$, closing $79.1\%$ of the gap at $100\%$ coverage. Restricting the same learner to one hop, on identical instances with the same decoder and demonstrations, collapses it to $1.344$, far worse than greedy. Two transfer checks target real-world networks. OLSRv2's unmodified selection code matches our cardinality greedy on $200/200$ unit-cost instances, and on $40{,}308$ instances of real battalion mobility the frozen model closes $48\%$ of the gap at full coverage. The information horizon, not the model capacity, is the most significant variable.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-10-02 in cs.AI).
Categorie arXiv: Machine Learning (stat.ML) ; Artificial Intelligence (cs.AI); Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.00422 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T10:21:28.066Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).