{"ID":2856879,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.01863","arxiv_id":"2511.01863","title":"SPHERE: Spherical partitioning for large-scale routing optimization","abstract":"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.","short_abstract":"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 s...","url_abs":"https://arxiv.org/abs/2511.01863","url_pdf":"https://arxiv.org/pdf/2511.01863v2","authors":"[\"Robert Fabian Lindermann\",\"Paul-Niklas Ken Kandora\",\"Simon Caspar Zeller\",\"Adrian Asmund Fessler\",\"Steffen Rebennack\"]","published":"2025-10-12T19:13:13Z","proceeding":"cs.DC","tasks":"[\"cs.DC\",\"cs.DM\"]","methods":"[]","has_code":false}