Approximating the Network Design Problem for Potential-Based Flows
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909000951398400 |
|---|---|
| author | Klimm, Max Pfetsch, Marc E. Skutella, Martin Strubberg, Lea |
| author_facet | Klimm, Max Pfetsch, Marc E. Skutella, Martin Strubberg, Lea |
| contents | We develop efficient algorithms for a fundamental network design problem arising in potential-based flow models, which are central to many energy transport networks (e.g., hydrogen and electricity). In contrast to classical network flow problems, the nonlinearities inherent in potential-based networks introduce significant new challenges. We address these challenges through intricate reductions to classical combinatorial optimization problems, such as (constrained) shortest path problems, enabling the application of well-established algorithmic techniques to compute exact and approximate solutions efficiently. Finally, we complement these algorithmic results with matching complexity results concerning the hardness and non-approximability of the considered problem variants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_26882 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Approximating the Network Design Problem for Potential-Based Flows Klimm, Max Pfetsch, Marc E. Skutella, Martin Strubberg, Lea Discrete Mathematics Combinatorics We develop efficient algorithms for a fundamental network design problem arising in potential-based flow models, which are central to many energy transport networks (e.g., hydrogen and electricity). In contrast to classical network flow problems, the nonlinearities inherent in potential-based networks introduce significant new challenges. We address these challenges through intricate reductions to classical combinatorial optimization problems, such as (constrained) shortest path problems, enabling the application of well-established algorithmic techniques to compute exact and approximate solutions efficiently. Finally, we complement these algorithmic results with matching complexity results concerning the hardness and non-approximability of the considered problem variants. |
| title | Approximating the Network Design Problem for Potential-Based Flows |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2604.26882 |