SPHERE: Spherical partitioning for large-scale routing optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910051237625856 |
|---|---|
| author | Lindermann, Robert Fabian Kandora, Paul-Niklas Ken Zeller, Simon Caspar Fessler, Adrian Asmund Rebennack, Steffen |
| author_facet | Lindermann, Robert Fabian Kandora, Paul-Niklas Ken Zeller, Simon Caspar Fessler, Adrian Asmund Rebennack, Steffen |
| contents | We study shortest-path routing in large weighted, undirected graphs, where expanding search frontiers raise time and memory costs for exact solvers. We propose \emph{SPHERE}, a query-aware partitioning heuristic that adaptively splits the problem by identifying \emph{source-target} ($s$--$t$) overlaps of hop-distance spheres. Selecting an anchor node $a$ within this overlap partitions the task into independent induced subgraphs for $s\to a$ and $a\to t$, each restricted to its own induced subgraph. If resulting subgraphs remain large, the procedure recurses on that specific subgraph. We provide a formal guarantee that by using the partition cut within the shared overlap, the resulting subpaths preserve feasibility, thereby avoiding the need for boundary repair. Furthermore, \emph{SPHERE} acts as a solver-agnostic framework that naturally exposes parallelism across subproblems. On million-scale road networks, \emph{SPHERE} achieves faster runtimes and smaller optimality gaps than contemporary state-of-the-art partitioning and community-based routing pipelines. Crucially, it also substantially mitigates heavy-tail runtime outliers suffered by standard exact methods, yielding highly stable and predictable execution times across varying queries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_01863 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | SPHERE: Spherical partitioning for large-scale routing optimization Lindermann, Robert Fabian Kandora, Paul-Niklas Ken Zeller, Simon Caspar Fessler, Adrian Asmund Rebennack, Steffen Distributed, Parallel, and Cluster Computing Discrete Mathematics We study shortest-path routing in large weighted, undirected graphs, where expanding search frontiers raise time and memory costs for exact solvers. We propose \emph{SPHERE}, a query-aware partitioning heuristic that adaptively splits the problem by identifying \emph{source-target} ($s$--$t$) overlaps of hop-distance spheres. Selecting an anchor node $a$ within this overlap partitions the task into independent induced subgraphs for $s\to a$ and $a\to t$, each restricted to its own induced subgraph. If resulting subgraphs remain large, the procedure recurses on that specific subgraph. We provide a formal guarantee that by using the partition cut within the shared overlap, the resulting subpaths preserve feasibility, thereby avoiding the need for boundary repair. Furthermore, \emph{SPHERE} acts as a solver-agnostic framework that naturally exposes parallelism across subproblems. On million-scale road networks, \emph{SPHERE} achieves faster runtimes and smaller optimality gaps than contemporary state-of-the-art partitioning and community-based routing pipelines. Crucially, it also substantially mitigates heavy-tail runtime outliers suffered by standard exact methods, yielding highly stable and predictable execution times across varying queries. |
| title | SPHERE: Spherical partitioning for large-scale routing optimization |
| topic | Distributed, Parallel, and Cluster Computing Discrete Mathematics |
| url | https://arxiv.org/abs/2511.01863 |