Approximating the Network Design Problem for Potential-Based Flows

2026/04/29 by Max Klimm, Marc E. Pfetsch, Martin Skutella +1 · 1 voice
Computer Science · Mathematics · #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.2604.26882

Abstract

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.

Citations

• Valid Cuts for the Design of Potential-based Flow Networks
• A reformulation-enumeration MINLP algorithm for gas network design
• Network design for s-t effective resistance
• Improved Approximation Schemes for the Restricted Shortest Path Problem
• Complexity and Approximation of the Continuous Network Design Problem
• The Steiner tree problem on graphs: Inapproximability results
• Approximation Schemes for the Restricted Shortest Path Problem

Discussions

• Max Klimm, Marc E. Pfetsch, Martin Skutella, Lea Strubberg: Approximating the Network Design Problem for Potential-Based Flows https://arxiv.org/abs/2604.26882 https://arxiv.org/pdf/2604.26882 https:/ [bsky, 0 points, 0 comments]

Related

• Valid Cuts for the Design of Potential-based Flow Networks
• Chance-Constrained Optimization for Non-Linear Network Flow Problems
• Adjustable Robust Nonlinear Network Design Without Controllable Elements under Load Scenario Uncertainties
• Finding a Feasible Flow in a Strongly Connected Network
• The Solution of Potential-Driven, Steady-State Nonlinear Network Flow Equations via Graph Partitioning