Designing Capacitated Subnetworks for Shortest Path Routing
Markus Chimani, Max Ilsen · 2026
Read Designing Capacitated Subnetworks for Shortest Path Routing by Markus Chimani, Max Ilsen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06319.txt.
Description
Markus Chimani and Max Ilsen tackle green traffic engineering for computer networks under shortest path routing. To save energy, operators want to switch off network links in quiet hours while still routing every demand that arrives. That means solving a design problem, which links to deactivate, and a routing problem together. For the common shortest path paradigm, no method handled the combined problem as a whole until now.
Their exact algorithm rests on a new integer linear program that models shortest paths changing dynamically as links drop. A special purpose column generation method solves it, strengthened by extra provably valid constraints. With true optima available for small practical cases, they benchmark the simpler heuristics used in practice. One simple fix the routing first method lands surprisingly close to optimal.
Catalog record
| CREATOR | Markus Chimani, Max Ilsen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06319