Svenja M. Griesbach

 

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

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

Teaching

• Teaching assistant for the lecture Computerorientierte Mathematik I
  Winter 23/24
• Teaching assistant for the lecture Discrete Optimization (ADM II)
  Summer 2022
• Teaching assistant for the lecture Introduction to Linear and Discrete Optimization (ADM I)
  Winter 21/22

Projects

• Information Design for Bayesian Networks
  Math+ project AA3-9. Project head: Max Klimm

Publications

to appear

• Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem (Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz)
  ESA 2024 – Proc. 32nd European Symposium on Algorithms.
  Bibtex Abstract
  @inproceedings{DisserGriesbachKlimm+2024,
  author = {Yann Disser and Svenja M. Griesbach and Max Klimm and Annette Lutz},
  title = {Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem},
  booktitle = {ESA 2024 – Proc. 32nd European Symposium on Algorithms},
  year = {to appear},
  }
  
  We consider an incremental variant of the rooted prize-collecting Steiner-tree problem with a growing budget constraint. While no incremental solution exists that simultaneously approximates the optimum for all budgets, we show that a bicriterial $(\alpha,\mu)$-approximation is possible, i.e., a solution that with budget $B+\alpha$ for all $B \in \R_{\geq 0}$ is a $\mu$-approximation compared to the optimum solution with budget $B$. For the case that the underlying graph is a tree, we present a polynomial density-greedy algorithm that computes a $(\chi,1)$-approximation, where $\chi$ denotes the eccentricity of the root vertex in the underlying graph, and show that this is best possible. An adaptation of the density-greedy algorithm for general graphs is $(\gamma,2)$-competitive where $\gamma$ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm is not polynomial, it can be adapted to a $(\gamma,3)$-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a $(3\chi,8)$-approximation and, more generally, a $\smash{((4\ell - 1)\chi, \frac{2^{\ell + 2}}{2^{\ell}-1})}$-approximation for every fixed $\ell \in \mathbb{N}$. A polynomial variant of this algorithm yields a $\smash{((4\ell - 1)\chi, \frac{2^{\ell + 3}}{2^{\ell}-1})}$-approximation.
• Optimizing Throughput and Makespan of Queuing Systems by Information Design (Svenja M. Griesbach, Max Klimm, Philipp Warode, and Theresa Ziemke)
  ESA 2024 – Proc. 32nd European Symposium on Algorithms.
  Bibtex Abstract
  @inproceedings{GriesbachKlimmWarode+2024,
  author = {Svenja M. Griesbach and Max Klimm and Philipp Warode and Theresa Ziemke},
  title = {Optimizing Throughput and Makespan of Queuing Systems by Information Design},
  booktitle = {ESA 2024 – Proc. 32nd European Symposium on Algorithms},
  year = {to appear},
  }
  
  We study the optimal provision of information for two natural performance measures of queuing systems: throughput and makespan. A set of parallel links (queues) is equipped with deterministic capacities and stochastic travel times where the latter depend on a realized scenario, and the number of scenarios is assumed to be constant. A continuum of flow particles (users) arrives at the system at a constant rate. A system operator knows the realization of the scenario and may (partially) reveal this information via a public signaling scheme to the flow particles. Upon arrival, the flow particles observe the signal issued by the system operator, form an updated belief about the realized scenario, and decide on a link to use. Inflow into a link exceeding the link's capacity builds up in a queue that increases the travel time on the link. Dynamic inflow rates are in a Bayesian dynamic equilibrium when the expected travel time along all links with positive inflow is equal at every point in time. For a given time horizon $T$, the throughput induced by a signaling scheme is the total volume of flow that leaves the links in the interval $[0,T]$. We show that the public signaling scheme that maximizes the throughput may involve irrational numbers and provide an additive polynomial time approximation scheme (PTAS) that approximates the optimal throughput by an arbitrary additive constant $\epsilon>0$. The algorithm solves a Langrangian dual of the signaling problem with the Ellipsoid method whose separation oracle is implemented by a cell decomposition technique. We also provide a multiplicative fully polynomial time approximation scheme (FPTAS) that does not rely on strong duality and, thus, allows to compute also the optimal signals. It uses a different cell decomposition technique together with a piece-wise convex under-estimator of the optimal value function. Finally, we consider the makespan of a Bayesian dynamic equilibrium which is defined as the last point in time when a total given value of flow leaves the system. Using a variational inequality argument, we show that full information revelation is a public signaling scheme that minimizes the makespan.

2024

• Deterministic Impartial Selection with Weights (Javier Cembrano, Svenja M. Griesbach, and Maximilian J. Stahlberg)
  ACM Transactions on Economics and Computation, 12(3):10:1–10:22, 2024.
  PDF DOI arxiv Preliminary version (WINE 2023) Bibtex Abstract
  @article{CembranoGriesbachStahlberg2024,
  author = {Javier Cembrano and Svenja M. Griesbach and Maximilian J. Stahlberg},
  title = {Deterministic Impartial Selection with Weights},
  journal = {ACM Transactions on Economics and Computation},
  year = {2024},
  volume = {12},
  number = {3},
  pages = {10:1--10:22},
  doi = {10.1145/3677177},
  arxiv = {2310.14991},
  }
  
  In the impartial selection problem, a subset of agents up to a fixed size $k$ among a group of $n$ is to be chosen based on votes cast by the agents themselves. A selection mechanism is \emphimpartial if no agent can influence its own chance of being selected by changing its vote. It is \emph$\alpha$-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of $\alpha$ of the votes received by the subset of size $k$ with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted votes and provide the first approximation guarantee, roughly $1/\lceil 2n/k\rceil$. When the number of agents to select is large enough compared to the total number of agents, this yields an improvement on the previously best known approximation ratio of $1/k$ for the unweighted setting. We further show that our mechanism can be adapted to the impartial assignment problem, in which multiple sets of up to $k$ agents are to be selected, with a loss in the approximation ratio of $1/2$.
• Book Embeddings of $k$-Framed Graphs and $k$-Map Graphs (Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou)
  Discrete Mathematics, 347:113690, 2024.
  PDF DOI Bibtex Abstract
  @article{BekosLozzoGriesbach+2024,
  author = {Michael A. Bekos and Giordano Da Lozzo and Svenja M. Griesbach and Martin Gronemann and Fabrizio Montecchiani and Chrysanthi Raftopoulou},
  title = {Book Embeddings of $k$-Framed Graphs and $k$-Map Graphs},
  journal = {Discrete Mathematics},
  doi = {10.1016/j.disc.2023.113690},
  volume = {347},
  issue = {1},
  pages = {113690},
  year = {2024},
  }
  
  An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, namely to $k$-map graphs. In fact, our technique can deal with any nonplanar graph having a biconnected skeleton of crossing-free edges whose faces have bounded degree. We prove that this family of graphs has book thickness bounded in $k$, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal $2$-planar graphs.
• Information Design for Congestion Games with Unknown Demand (Svenja M. Griesbach, Martin Hoefer, Max Klimm, and Tim Koglin)
  AAAI 2024 – Proc. 38th Annual Conference on Artificial Intelligence, pp. 9722–9730.
  PDF DOI Bibtex Abstract
  @inproceedings{GriesbachHoeferKlimm+2024,
  author = {Svenja M. Griesbach and Martin Hoefer and Max Klimm and Tim Koglin},
  title = {Information Design for Congestion Games with Unknown Demand},
  booktitle = {AAAI 2024 – Proc. 38th Annual Conference on Artificial Intelligence},
  year = {2024},
  pages = {9722--9730},
  doi = {10.1609/aaai.v38i9.28830},
  }
  
  We study a novel approach to information design in the standard traffic model of network congestion games. It captures the natural condition that the demand is unknown to the users of the network. A principal (e.g., a mobility service) commits to a signaling strategy, observes the realized demand and sends a (public) signal to agents (i.e., users of the network). Based on the induced belief about the demand, the users then form an equilibrium. We consider the algorithmic goal of the principal: Compute a signaling scheme that minimizes the expected total cost of the induced equilibrium. We concentrate on single-commodity networks and affine cost functions, for which we obtain the following results. First, we devise a fully polynomial-time approximation scheme (FPTAS) for the case that the demand can only take two values. It relies on several structural properties of the cost of the induced equilibrium as a function of the updated belief about the distribution of demands. We show that this function is piecewise linear for any number of demands, and monotonic for two demands. Second, we give a complete characterization of the graph structures for which it is optimal to fully reveal the information about the realized demand. This signaling scheme turns out to be optimal for all cost functions and probability distributions over demands if and only if the graph is series-parallel. Third, we propose an algorithm that computes the optimal signaling scheme for any number of demands whose time complexity is polynomial in the number of supports that occur in a Wardrop equilibrium for some demand. Finally, we conduct a computational study that tests this algorithm on real-world instances.

2023

• Improved Approximation Algorithms for the Expanding Search Problem (Svenja M. Griesbach, Felix Hommelsheim, Max Klimm, and Kevin Schewior)
  ESA 2023 – Proc. 31st European Symposium on Algorithms, pp. 54:1–54:15.
  PDF DOI Bibtex Abstract
  @inproceedings{GriesbachHommelsheimKlimm+2023,
  author = {Svenja M. Griesbach and Felix Hommelsheim and Max Klimm and Kevin Schewior},
  title = {Improved Approximation Algorithms for the Expanding Search Problem},
  booktitle = {ESA 2023 – Proc. 31st European Symposium on Algorithms},
  year = {2023},
  pages = {54:1--54:15},
  doi = {10.4230/LIPIcs.ESA.2023.54},
  }
  
  A searcher faces a graph with edge lengths and vertex weights, initially having explored only a given starting vertex. In each step, the searcher adds an edge to the solution that connects an unexplored vertex to an explored vertex. This requires an amount of time equal to the edge length. The goal is to minimize the weighted sum of the exploration times over all vertices. We show that this problem is hard to approximate and provide algorithms with improved approximation guarantees. For the general case, we give a $(2e+\varepsilon)$-approximation for any $\varepsilon > 0$. For the case that all vertices have unit weight, we provide a $2e$-approximation. Finally, we provide a PTAS for the case of a Euclidean graph. Previously, for all cases only an $8$-approximation was known.
• Deterministic Impartial Selection with Weights (Javier Cembrano, Svenja M. Griesbach, and Maximilian J. Stahlberg)
  WINE 2023 – Proc. 19th Conference on Web and Internet Economics, Springer Nature Switzerland, pp. 151–168.
  PDF DOI arxiv Extended version (TEAC 2024) Bibtex Abstract
  @inproceedings{CembranoGriesbachStahlberg2023,
  author = {Javier Cembrano and Svenja M. Griesbach and Maximilian J. Stahlberg},
  title = {Deterministic Impartial Selection with Weights},
  editor = {Jugal Garg and Max Klimm and Yuqing Kong},
  booktitle = {WINE 2023 – Proc. 19th Conference on Web and Internet Economics},
  series = {LNCS},
  volume = {14413},
  publisher = {Springer Nature Switzerland},
  address = {Cham},
  year = {2023},
  pages = {151--168},
  doi = {10.1007/978-3-031-48974-7\_9},
  arxiv = {2310.14991},
  }
  
  In the impartial selection problem, a subset of agents up to a fixed size $k$ among a group of $n$ is to be chosen based on votes cast by the agents themselves. A selection mechanism is impartial if no agent can influence its own chance of being selected by changing its vote. It is $\alpha$-optimal if, for every instance, the ratio between the votes received by the selected subset is at least a fraction of $\alpha$ of the votes received by the subset of size $k$ with the highest number of votes. We study deterministic impartial mechanisms in a more general setting with arbitrarily weighted votes and provide the first approximation guarantee, roughly $1/\lceil 2n/k\rceil$. When the number of agents to select is large enough compared to the total number of agents, this yields an improvement on the previously best known approximation ratio of $1/k$ for the unweighted setting. We further show that our mechanism can be adapted to the impartial assignment problem, in which multiple sets of up to $k$ agents are to be selected, with a loss in the approximation ratio of $1/2$.

2022

• Public Signals in Network Congestion Games (Svenja M. Griesbach, Martin Hoefer, Max Klimm, and Tim Koglin)
  EC 2022 – Proc. 23rd ACM Conference on Economics and Computation, pp. 736.
  PDF DOI arxiv Bibtex Abstract
  @inproceedings{GriesbachHoeferKlimm+2022,
  arxiv = {2205.09823},
  author = {Svenja M. Griesbach and Martin Hoefer and Max Klimm and Tim Koglin},
  booktitle = {EC 2022 – Proc. 23rd ACM Conference on Economics and Computation},
  doi = {10.1145/3490486.3538349},
  pages = {736},
  title = {Public Signals in Network Congestion Games},
  year = {2022},
  }
  
  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.

2020

• Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages (Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou)
  SoCG 2020 – Proc. 36th International Symposium on Computational Geometry, pp. 16:1–16:17.
  DOI Bibtex Abstract
  @inproceedings{BekosDaLozzoGriesbach+2020,
  address = {Dagstuhl, Germany},
  annote = {Keywords: Book embeddings, Book thickness, Nonplanar graphs, Planar skeleton},
  author = {Michael A. Bekos and Giordano Da Lozzo and Svenja M. Griesbach and Martin Gronemann and Fabrizio Montecchiani and Chrysanthi Raftopoulou},
  booktitle = {SoCG 2020 – Proc. 36th International Symposium on Computational Geometry},
  doi = {10.4230/LIPIcs.SoCG.2020.16},
  editor = {Sergio Cabello and Danny Z. Chen},
  pages = {16:1--16:17},
  title = {Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages},
  urn = {urn:nbn:de:0030-drops-121749},
  volume = {164},
  year = {2020},
  }
  
  An embedding of a graph in a book, called book embedding, consists of a linear ordering of its vertices along the spine of the book and an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. For planar graphs, a fundamental result is due to Yannakakis, who proposed an algorithm to compute embeddings of planar graphs in books with four pages. Our main contribution is a technique that generalizes this result to a much wider family of nonplanar graphs, which is characterized by a biconnected skeleton of crossing-free edges whose faces have bounded degree. Notably, this family includes all 1-planar and all optimal 2-planar graphs as subgraphs. We prove that this family of graphs has bounded book thickness, and as a corollary, we obtain the first constant upper bound for the book thickness of optimal 2-planar graphs.

Recent Talks

• Optimizing Throughput and Makespan of Queuing Systems by Information Design, Dagstuhl Seminar on Dynamic Traffic Models in Transportation Science, 11. Jul 24
• Deterministic Impartial Selection with Weights, Klagenfurt-Berlin Workshop on Multiple Perspectives in Optimization, 06. Jun 24
• Optimizing Throughput and Makespan of Queuing Systems by Information Design, 26th Combinatorial Optimization Workshop, 08. Jan 24
• Deterministic Impartial Selection with Weights, WINE 2023, 05. Dec 23
• Improved Approximation Algorithms for the Expanding Search Problem, ESA 2023, 05. Sep 23
• Improved Approximation Algorithms for the Expanding Search Problem, International Conference on Operations Research, 30. Aug 23
• Information Design for Congestion Games with Unknown Demand, ICALP Workshop on Congestion Games, 10. Jul 23
• Information Design for Bayesian Networks, Math+ Spotlight Talk Series, 14. Jun 23
• Improved Approximation Algorithms for the Expanding Search Problem, University of Bremen, 27. Apr 23
• Public Signals in Network Congestion Games, 3rd GOR Meeting on Game Theory and Behavioral Management Science, 31. Jan 23
• Public Signals in Network Congestion Games, DMV Annual Meeting 2022, 16. Sep 22
• Public Signals in Network Congestion Games, EC 2022, 13. Jul 22