Approximating the Network Design Problem for Potential-Based Flows
2026-04-29 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study a network design problem found in energy transport systems like hydrogen and electricity networks, which involve flows driven by potentials (like voltages or pressures). Unlike simpler flow problems, these have nonlinear behaviors that make them harder to solve. They cleverly transform these tricky problems into more familiar ones, such as shortest path problems, allowing the use of known algorithms to find exact or approximate solutions efficiently. They also prove theoretical results about how hard some versions of these problems are to solve or approximate.
network designpotential-based flowenergy transport networksnonlinear optimizationshortest path problemcombinatorial optimizationexact algorithmsapproximation algorithmscomputational complexitynon-approximability
Authors
Max Klimm, Marc E. Pfetsch, Martin Skutella, Lea Strubberg
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.