Faculties
DE / EN

## Maximilian J. Stahlberg

Research assistant

Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Office: MA 505
Telephone: +49 30 314 25739
Email: (lastname)@math.tu-berlin.de

### Publications

• Spatiotemporal reconstruction of ancient road networks through sequential cost–benefit analysis (, , and )
PNAS Nexus, .
@article{StahlbergSagnolDuckeKlimm2022,
author = {Maximilian J. Stahlberg and Guillaume Sagnol and Benjamin Ducke and Max Klimm},
title = {Spatiotemporal reconstruction of ancient road networks through sequential cost--benefit analysis},
journal = {PNAS Nexus},
year = {to appear},
accepted = {20.12.2022},
}
The construction of ancient road networks spanned generations and exhibits temporal path dependence that is not fully captured by established network formation models that are used to support archaeological reasoning. We introduce an evolutionary model that captures explicitly the sequential nature of road network formation: A central feature is that connections are added successively and according to an optimal cost–benefit trade-off with respect to existing connections. In this model, the network topology emerges rapidly from early decisions, a trait that makes it possible to identify plausible road construction orders in practice. Based on this observation we develop a method to compress the search space of path-dependent optimization problems. We use this method to show that the model's assumptions on ancient decision making allow the reconstruction of partially known road networks from the Roman era in good detail and from sparse archaeological evidence. In particular, we identify missing links in the major road network of ancient Sardinia that are in good agreement with expert predictions.
• PICOS: A Python interface to conic optimization solvers ( and )
Journal of Open Source Software, 7(70):3915, .
@article{SagnolStahlberg2022,
author = {Guillaume Sagnol and Maximilian J. Stahlberg},
doi = {10.21105/joss.03915},
journal = {Journal of Open Source Software},
number = {70},
pages = {3915},
title = {{PICOS}: A {Python} interface to conic optimization solvers},
volume = {7},
year = {2022},
}
Many convex and mixed integer constrained optimization problems can be compiled into a canonical form and handed to some off-the-shelf optimization solver for numeric solution. However, the necessary reformulations can be technically challenging and a program written to use one solver cannot easily be made to use another. PICOS is a well-established Python meta-interface to many proprietary and open source optimization solvers that allows problems to be input in a natural algebraic form and that handles solver selection and the required transformations transparently. This enables users to focus more on the high level optimization model and its application and less on technicalities.
• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths (, , , and )
Networks, 73(1):23–37, .
@article{BazganFluschnikNichterlein+2019,
arxiv = {1804.09155},
author = {Cristina Bazgan and Till Fluschnik and Andr{\'e} Nichterlein and Rolf Niedermeier and Maximilian J. Stahlberg},
doi = {10.1002/net.21832},
journal = {Networks},
number = {1},
pages = {23--37},
title = {A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths},
volume = {73},
year = {2019},
}
We study the $\mathsf{NP}$-hard shortest path most vital edges problem arising in the context of analyzing network robustness. For an undirected graph with positive integer edge lengths and two designated vertices s and t, the goal is to delete as few edges as possible in order to increase the length of the (new) shortest $st$-path as much as possible. This scenario has been studied from the viewpoint of parameterized complexity and approximation algorithms. We contribute to this line of research by providing refined computational tractability as well as hardness results. We achieve this by a systematic investigation of various problem-specific parameters and their influence on the computational complexity. Charting the border between tractability and intractability, we also identify numerous challenges for future research.

### Theses

• Robust conic optimization in Python (Maximilian J. Stahlberg)
Master's thesis, 2020.
• Finding the Most Vital Edges for Shortest Paths: Algorithms and Complexity for Special Graph Classes (Maximilian J. Stahlberg)
Bachelor's thesis, 2016.

### Software

• PICOS (Guillaume Sagnol and Maximilian J. Stahlberg)
A Python interface to conic optimization solvers.