Approximating the Network Design Problem for Potential-Based Flows
It addresses a fundamental design problem for energy transport networks (e.g., hydrogen and electricity) where nonlinearities pose new challenges.
The paper develops efficient algorithms for a network design problem in potential-based flow models, achieving exact and approximate solutions via reductions to classical combinatorial problems, and provides matching hardness results.
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.