### PhD position available

13. Oct 22A PhD position is available in the Discrete Optimization group at TU Berlin with ties to the Combinatorial Optimization and Graph Algorithms group. The successful applicant will participate in research project A07 in the frame of the DFG-funded Transregio TRR 154. The task of the successful applicant is to study combinatorial optimization problems that arise, for example, in the construction and operation of new hydrogen networks or other gas networks. The opportunity to prepare a PhD thesis will be provided.

##### Requirements

- succesfully completed university degree (Master, Diplom or equivalent) in Mathematics, Computer Science or related fields; clearly above-average grades are desired
- profound knowledge in Discrete Mathematics, Algorithm Design and Algorithm Analysis are desirable
- knowledge in the field of Optimization or related areas is desirable
- good command of German and/or English required; willingness to learn either English or German is expected

The application deadline is: November 18, 2022. Informal inquires about the position can be directed at any time to Max Klimm. Please also send a mail if you would like to apply but have difficulties in meeting the application deadline or are still missing your final exam but expect to obtain it soon.

Besides its many cultural attractions, Berlin offers a strong scientific landscape including three major universities, the DFG funded mathematics research center MATH+ as well as the international graduate program Berlin Mathematical School; these offer opportunities for joint research and support for PhD students (e.g., meetings, lecture series, international summer schools etc.).### Application Deadline for BMS

01. Dec 22#### Berlin Mathematical School (BMS) – Get Your Math PhD in Berlin

The Berlin Mathematical School is the graduate school of the Cluster of Excellence MATH+ and a joint endeavor of the mathematics departments at the universities in Berlin: Freie Universität (FU), Humboldt-Universität (HU) and Technische Universität (TU).

We offer an excellent doctoral program taught in English in a broad and active research environment together with mentoring programs, language courses, soft-skills seminars, funding for summer schools and conferences, a buddy program and funding for students with children.

“Mathematics as a whole“ is a leading principle of the BMS. Its focus encompasses fields that are traditionally termed “pure“ or “applied“ mathematics, though we prefer not to make that distinction. Instead, research topics are grouped into eight parts, each covering a broad, but coherent, part of mathematics:- Differential geometry, global analysis, and mathematical physics
- Algebraic and arithmetic geometry, number theory
- Stochastics and mathematical finance
- Discrete mathematics and optimization
- Geometry, topology, and visualization
- Numerical analysis and scientific computing
- Applied analysis and differential equations
- Mathematics of data science

All you need to know about applying to the BMS is available online . You can apply here .##### Application Deadlines

The first round application deadline of 1 December 2022 is for- Phase I applicants requiring admission with scholarship
- Phase II who want to start before August 2023.

- Phase I applicants requiring admission only
- Phase II applicants who want to start in August, September or October 2023.

### Paper accepted at Mathematics of Operations Research

29. Oct 22The paper Reduction of Potential-Based Flow Networks by Max Klimm, Marc Pfetsch, Rico Raber and Martin Skutella has been accepted at Mathematics of Operations Research

##### Abstract of the paper

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.

### PostDoc position available

13. Oct 22We are looking for a candidate with extensive experience and independent research results in the field of “Optimization under Uncertainty”, for example, in the field of Robust Optimization, Data-driven Optimization, Online Algorithms, and Algorithmic Game Theory.

##### Requirements

- Dissertation in Mathematics, Computer Science or related disciplines
- Research experience in “Optimization under Uncertainty”, publications in top-tier journals, and conference proceedings
- Excellent written and spoken English
- Applicants should be interested in cooperations with other scientific disciplines as well as with industry and commercial enterprises. Moreover, they should be distinguished by an excellent doctorate and their own research results in this area and should have achieved initial international visibility.

You can find the official job announcement and information about the application procedure here. The application deadline is 11 November 2022.### Paper accepted at SIAM Journal on Applied Algebra and Geometry

30. Sep 22The paper Generalized permutahedra and optimal auctions by Michael Joswig, Max Klimm and Sylvain Spitz has been accepted at SIAM Journal on Applied Algebra and Geometry

##### Abstract of the paper

We study a family of convex polytopes, called SIM-bodies, which were introduced by Giannakopoulos and Koutsoupias (2018) to analyze so-called Straight-Jacket Auctions. First, we show that the SIM-bodies belong to the class of generalized permutahedra. Second, we prove an optimality result for the Straight-Jacket Auctions among certain deterministic auctions. Third, we employ computer algebra methods and mathematical software to explicitly determine optimal prices and revenues.

### Virtual talk at APPROX 2022

21. Sep 22Martin Knaack will present the paper "Maximizing a submodular function with bounded curvature under an unknown knapsack constraint" (joint work with Max Klimm) at this year's APPROX conference.

##### Abstract of the talk

We study the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature $c$ of the submodular function. For the extreme cases $c=0$ corresponding to a modular objective, it matches a previously known and best possible robustness factor of $1/2$. For the other extreme case of $c=1$ it yields a robustness factor of $\approx 0.35$ improving over the best previously known robustness factor of $\approx 0.06$.

### Talk at DMV Meeting 2022

16. Sep 22Svenja Griesbach will give a talk "Public signals in network congestion games" (joint work with Martin Hoefer, Tim Koglin, and Max Klimm) at the annual meeting of the DMV.

##### Abstract of the talk

We consider a largely untapped potential for the improvement of traffic networks that is rooted in the inherent uncertainty of travel times. Travel times are subject to stochastic uncertainty resulting from various parameters such as weather condition, occurrences of road works, or traffic accidents. Large mobility services have an informational advantage over single network users as they are able to learn traffic conditions from data. A benevolent mobility service may use this informational advantage in order to steer the traffic equilibrium into a favorable direction. The resulting optimization problem is a task commonly referred to as signaling or Bayesian persuasion. Previous work has shown that the underlying signaling problem can be NP-hard to approximate within any non-trivial bounds, even for affine cost functions with stochastic offsets. In contrast, we show that in this case, the signaling problem is easy for many networks. We tightly characterize the class of single-commodity networks, in which full information revelation is always an optimal signaling strategy. Moreover, we construct a reduction from optimal signaling to computing an optimal collection of support vectors for the Wardrop equilibrium. For two states, this insight can be used to compute an optimal signaling scheme. The algorithm runs in polynomial time whenever the number of different supports resulting from any signal distribution is bounded to a polynomial in the input size. Using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multi-commodity parallel link networks with a constant number of commodities, even when we have a constant number of different states of nature.

### Talk at DMV Meeting 2022

14. Sep 22Sylvain Spitz will give a talk "Generalized permutahedra and optimal auctions" (joint work with Michael Joswig and Max Klimm) at the annual meeting of the DMV.

##### Abstract of the talk

We study a family of convex polytopes, called SIM-bodies that were introduced by Giannakopoulos and Koutsoupias (2018) to analyze so-calles Straight-Jacket Auctions. First, we show that the SIM-bodies belong to the class of generalized permutahedra. Second, we prove an optimality result for Straight-Jacket Auctions among certain deterministic auctions. Third, we emply computer algebra methods and mathematical software to explicitly determine optimal prices and revenues.

### Paper accepted at WINE 2022

07. Sep 22The paper Optimal Impartial Correspondences by Javier Cembrano, Felix A. Fischer and Max Klimm has been accepted at WINE 2022

##### Abstract of the paper

We study mechanisms that select a subset of the vertex set of a directed graph in order to maximize the minimum indegree of any selected vertex, subject to an impartiality constraint that the selection of a particular vertex is independent of the outgoing edges of that vertex. For graphs with maximum outdegree $d$, we give a mechanism that selects at most $d+1$ vertices and only selects vertices whose indegree is at least the maximum indegree in the graph minus one. We then show that this is best possible in the sense that no impartial mechanism can only select vertices with maximum degree, even without any restriction on the number of selected vertices. We finally obtain the following trade-off between the maximum number of vertices selected and the minimum indegree of any selected vertex: when selecting at most $k$ of vertices out of $n$, it is possible to only select vertices whose indegree is at least the maximum indegree minus $\lfloor(n-2)/(k-1)\rfloor+1$.

### Talk at EC 2022

14. Jul 22Javier Cembrano presented the paper "Impartial selection with additive guarantees via iterated deletion" (joint work with Felix Fischer, David Hannon, and Max Klimm) at this year's EC conference.

##### Abstract of the talk

Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $\mathcal{O}(n^{(1+\kappa)/2})$ in a setting with $n$ individuals where each individual casts $\mathcal{O}(n^\kappa)$ nominations, where $\kappa \in [0,1]$. For $\kappa=0$, i.e. when each individual casts at most a constant number of nominations, this bound is $\mathcal{O}(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\kappa=1$ the bound is $\mathcal{O}(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.

### Talk at EC 2022

13. Jul 22Svenja Griesbach presented the paper "Public signals in network congestion games" (joint work with Martin Hoefer, Tim Koglin, and Max Klimm) at this year's EC conference.

##### Abstract of the paper

We consider a largely untapped potential for the improvement of traffic networks that is rooted in the inherent uncertainty of travel times. Travel times are subject to stochastic uncertainty resulting from various parameters such as weather condition, occurrences of road works, or traffic accidents. Large mobility services have an informational advantage over single network users as they are able to learn traffic conditions from data. A benevolent mobility service may use this informational advantage in order to steer the traffic equilibrium into a favorable direction. The resulting optimization problem is a task commonly referred to as signaling or Bayesian persuasion. Previous work has shown that the underlying signaling problem can be NP-hard to approximate within any non-trivial bounds, even for affine cost functions with stochastic offsets. In contrast, we show that in this case, the signaling problem is easy for many networks. We tightly characterize the class of single-commodity networks, in which full information revelation is always an optimal signaling strategy. Moreover, we construct a reduction from optimal signaling to computing an optimal collection of support vectors for the Wardrop equilibrium. For two states, this insight can be used to compute an optimal signaling scheme. The algorithm runs in polynomial time whenever the number of different supports resulting from any signal distribution is bounded to a polynomial in the input size. Using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multi-commodity parallel link networks with a constant number of commodities, even when we have a constant number of different states of nature.

### Paper accepted at APPROX 2022

22. Jun 22The paper Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint by Max Klimm and Martin Knaack has been accepted at APPROX 2022

##### Abstract of the paper

This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature $c$ of the submodular function. For the extreme cases $c = 0$ corresponding to a modular objective, it matches a previously known and best possible robustness factor of $1/2$. For the other extreme case of $c = 1$ it yields a robustness factor of $\approx 0.35$ improving over the best previously known robustness factor of $\approx 0.06$.

### Paper accepted at Optimization Methods and Software

20. Jun 22The paper Nonconvex Equilibrium Models for Energy Markets: Exploiting Price Information to Determine the Existence of an Equilibrium by Julia Grübel, Olivier Huber, Lukas Hümbs, Max Klimm, Martin Schmidt and Alexandra Schwartz has been accepted at Optimization Methods and Software

##### Abstract of the paper

Motivated by examples from the energy sector, we consider market equilibrium problems (MEPs) involving players with nonconvex strategy spaces or objective functions, where the latter are assumed to be linear in market prices. We propose an algorithm that determines if an equilibrium of such an MEP exists and that computes an equilibrium in case of existence. Three key prerequisites have to be met. First, appropriate bounds on market prices have to be derived from necessary optimality conditions of some players. Second, a technical assumption is required for those prices that are not uniquely determined by the derived bounds. Third, nonconvex optimization problems have to be solved to global optimality. We test the algorithm on well-known instances from the power and gas literature that meet these three prerequisites. There, nonconvexities arise from considering the transmission system operator as an additional player besides producers and consumers who, e.g., switches lines or faces nonlinear physical laws. Our numerical results indicate that equilibria often exist, especially for the case of continuous nonconvexities in the context of gas market problems.