- Reduction of Potential-Based Flow Networks ( )

Mathematics of Operations Research, to appear.

@article{KlimmPfetschRaber+2022,

author = {Max Klimm and Marc Pfetsch and Rico Raber and Martin Skutella},

title = {Reduction of Potential-Based Flow Networks},

journal = {Mathematics of Operations Research},

year = {to appear},

accepted = {29.10.2022},

}We consider potential-based flow networks with terminal nodes at which flow can enter or leave the network and physical properties such as voltages or pressures are measured and controlled. We study conditions under which such a network can be reduced to a smaller, equivalent network with the same behavior at the terminal nodes. Potential-based flow networks are widely used to model infrastructure networks such as electricity, gas, or water networks. In contrast to Kron's reduction for electrical networks, we prove that, in general, potential-based flow networks with at least three terminals cannot be reduced to smaller networks whose size only depends on the number of terminals. On the other hand, we show that it is possible to represent a special class of potential-based flow networks by a complete graph on the terminals, and we establish a characterization of networks that can be reduced to a path network. Our results build on fundamental properties of effective resistances proved in this paper, including explicit formulae for their dependence on edge resistances of the network and their metric properties.

- On the Robustness of Potential-Based Flow Networks ( )

Mathematical Programming, 197:337–374, 2023.

@article{KlimmPfetschRaber+2022a,

author = {Max Klimm and Marc E. Pfetsch and Rico Raber and Martin Skutella},

doi = {10.1007/s10107-021-01760-w},

journal = {Mathematical Programming},

title = {On the Robustness of Potential-Based Flow Networks},

year = {2023},

volume = {197},

pages = {337--374},

}Potential-based flows provide a simple yet realistic mathematical model of transport in many real-world infrastructure networks such as, e.g., gas or water networks, where the flow along each edge depends on the difference of the potentials at its end nodes. We call a network topology robust if the maximal node potential needed to satisfy a set of demands never increases when demands are decreased. This notion of robustness is motivated by infrastructure networks where users first make reservations for certain demands that may be larger than the actual flows sent later on. In these networks, node potentials correspond to physical quantities such as pressures or hydraulic heads and must be guaranteed to lie within a fixed range, even if the actual amounts are smaller than the previously reserved demands. Our main results are a precise characterization of robust network topologies for the case of point-to-point demands via forbidden node-labeled graph minors, as well as an efficient algorithm for testing robustness.

- Packing Under Convex Quadratic Constraints ( )

Mathematical Programming, 192:361–386, 2022.

@article{KlimmPfetschRaber+2022b,

author = {Max Klimm and Marc E. Pfetsch and Rico Raber and Martin Skutella},

doi = {10.1007/s10107-021-01675-6},

journal = {Mathematical Programming},

pages = {361--386},

title = {Packing Under Convex Quadratic Constraints},

volume = {192},

year = {2022},

}We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are $\mathsf{APX}$-hard to approximate and present constant-factor approximation algorithms based upon two different algorithmic techniques: a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation, and a greedy strategy. We further show that a combination of these techniques can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of these algorithms for problem instances arising in the context of real-world gas transport networks.

- Packing Under Convex Quadratic Constraints ( )

IPCO 2020 – Proc. 21st Conference on Integer Programming and Combinatorial Optimization, pp. 266–279.

@inproceedings{KlimmPfetschRaber+2020,

author = {Max Klimm and Marc E. Pfetsch and Rico Raber and Martin Skutella},

booktitle = {IPCO 2020 – Proc. 21st Conference on Integer Programming and Combinatorial Optimization},

doi = {10.1007/978-3-030-45771-6\_21},

pages = {266--279},

title = {Packing Under Convex Quadratic Constraints},

year = {2020},

}We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are $\mathsf{APX}$-hard to approximate and present constant-factor approximation algorithms based upon three different algorithmic techniques: (1) a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation whose approximation ratio equals the golden ratio; (2) a greedy strategy; (3) a randomized rounding method leading to an approximation algorithm for the more general case with multiple convex quadratic constraints. We further show that a combination of the first two strategies can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of the three algorithms for problem instances arising in the context of real-world gas transport networks.

- MatchTheNet - An Educational Game on 3-Dimensional Polytopes (Multimedia Contribution) ( )

SoCG 2017 – Proc. 33rd International Symposium on Computational Geometry, pp. 66:1–66:5.

@inproceedings{JoswigLohoLorenz+2017,

author = {Michael Joswig and Georg Loho and Benjamin Lorenz and Rico Raber},

booktitle = {SoCG 2017 – Proc. 33rd International Symposium on Computational Geometry},

doi = {10.4230/LIPIcs.SoCG.2017.66},

editor = {Boris Aronov and Matthew J. Katz},

pages = {66:1--66:5},

series = {LIPIcs},

title = {MatchTheNet - An Educational Game on 3-Dimensional Polytopes (Multimedia Contribution)},

volume = {77},

year = {2017},

}We present an interactive game which challenges a single player to match 3-dimensional polytopes to their planar nets. It is open source, and it runs in standard web browsers.