7 Search Results for "Griesbach, Svenja M."

Document
DOI: 10.4230/LIPIcs.ESA.2025.34
On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem

Authors: Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, and Laura Vargas Koch

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In train routing, the headway is the minimum distance that must be maintained between successive trains for safety and robustness. We introduce a model for train routing that requires a fixed headway to be maintained between trains, and study the problem of minimizing the makespan, i.e., the arrival time of the last train, in a single-source single-sink network. For this problem, we first show that there exists an optimal solution where trains move in convoys - that is, the optimal paths for any two trains are either the same or are arc-disjoint. Via this insight, we are able to reduce the approximability of our train routing problem to that of the min-max disjoint paths problem, which asks for a collection of disjoint paths where the maximum length of any path in the collection is as small as possible. While min-max disjoint paths inherits a strong inapproximability result on directed acyclic graphs from the multi-level bottleneck assignment problem, we show that a natural greedy composition approach yields a logarithmic approximation in the number of disjoint paths for series-parallel graphs. We also present an alternative analysis of this approach that yields a guarantee depending on how often the decomposition tree of the series-parallel graph alternates between series and parallel compositions on any root-leaf path.
Cite as

Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, and Laura Vargas Koch. On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.ESA.2025.34,
  author =	{Bhaskar, Umang and Eickhoff, Katharina and Kauther, Lennart and Matuschke, Jannik and Peis, Britta and Vargas Koch, Laura},
  title =	{{On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.34},
  URN =		{urn:nbn:de:0030-drops-245029},
  doi =		{10.4230/LIPIcs.ESA.2025.34},
  annote =	{Keywords: Train Routing, Scheduling, Approximation Algorithms, Flows over Time, Min-Max Disjoint Paths}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.92
Incremental Maximization for a Broad Class of Objectives

Authors: Yann Disser and David Weckbecker

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider incremental maximization problems, where the solution has to be built up gradually by adding elements one after the other. In every step, the incremental solution must be competitive, compared against the optimum solution of the current cardinality. We prove that a competitive solution always exists when the objective function is monotone and β-accountable, by providing a scaling algorithm that guarantees a constant competitive ratio. This generalizes known results and, importantly, yields the first competitive algorithm for the natural class of monotone and subadditive objective functions.
Cite as

Yann Disser and David Weckbecker. Incremental Maximization for a Broad Class of Objectives. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 92:1-92:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{disser_et_al:LIPIcs.ESA.2025.92,
  author =	{Disser, Yann and Weckbecker, David},
  title =	{{Incremental Maximization for a Broad Class of Objectives}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{92:1--92:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.92},
  URN =		{urn:nbn:de:0030-drops-245613},
  doi =		{10.4230/LIPIcs.ESA.2025.92},
  annote =	{Keywords: incremental maximization, competitive analysis, subadditive functions}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.27
Cops and Robbers for Graphs on Surfaces with Crossings

Authors: Prosenjit Bose, Pat Morin, and Karthik Murali

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Cops and Robbers is a game played on a graph where a set of cops attempt to capture a single robber. The game proceeds in rounds, where each round first consists of the cops' turn, followed by the robber’s turn. In the first round, the cops place themselves on a subset of vertices, after which the robber chooses a vertex to place himself. From the next round onwards, in the cops' turn, every cop can choose to either stay on the same vertex or move to an adjacent vertex, and likewise the robber in his turn. The robber is considered to be captured if, at any point in time, there is some cop on the same vertex as the robber. The cops win if they can capture the robber within a finite number of rounds; else the robber wins. A natural question in this game concerns the cop-number of a graph - the minimum number of cops needed to capture a robber. It has long been known that graphs embeddable (without crossings) on surfaces of bounded genus have bounded cop-number. In contrast, it was shown recently that the class of 1-planar graphs - graphs that can be drawn on the plane with at most one crossing per edge - does not have bounded cop-number. This paper initiates an investigation into how the distance between crossing pairs of edges influences a graph’s cop number. In particular, we look at Distance d Cops and Robbers, a variant of the classical game, where the robber is considered to be captured if there is a cop within distance d of the robber. Let c_d(G) denote the minimum number of cops required in the graph G to capture a robber within distance d. We look at various classes of graphs, such as 1-plane graphs, k-plane graphs (graphs where each edge is crossed at most k times), and even general graph drawings, and show that if every crossing pair of edges can be connected by a path of small length, then c_d(G) is bounded, for small values of d. For example, we show that if a graph G admits a drawing in which every pair of crossing edges is contained in a path of length at most 3, then c₄(G) ≤ 21. And if the drawing permits a stronger assumption that the endpoints of every crossing induce the complete graph K₄, then c₃(G) ≤ 9. The tools and techniques that we develop in this paper are sufficiently general, enabling us to examine graphs drawn not only on the sphere but also on orientable and non-orientable surfaces.
Cite as

Prosenjit Bose, Pat Morin, and Karthik Murali. Cops and Robbers for Graphs on Surfaces with Crossings. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.MFCS.2025.27,
  author =	{Bose, Prosenjit and Morin, Pat and Murali, Karthik},
  title =	{{Cops and Robbers for Graphs on Surfaces with Crossings}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.27},
  URN =		{urn:nbn:de:0030-drops-241349},
  doi =		{10.4230/LIPIcs.MFCS.2025.27},
  annote =	{Keywords: Cops and Robbers, Crossings, 1-Planar, Surfaces}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.47
Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem

Authors: Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
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 (α,μ)-approximation is possible, i.e., a solution that with budget B+α for all B ∈ ℝ_{≥ 0} is a multiplicative μ-approximation compared to the optimum solution with budget B. For the case that the underlying graph is a tree, we present a polynomial-time density-greedy algorithm that computes a (χ,1)-approximation, where χ 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 (γ,2)-competitive where γ is the maximal length of a vertex-disjoint path starting in the root. While this algorithm does not run in polynomial time, it can be adapted to a (γ,3)-competitive algorithm that runs in polynomial time. We further devise a capacity-scaling algorithm that guarantees a (3χ,8)-approximation and, more generally, a ((4𝓁 - 1)χ, (2^{𝓁 + 2})/(2^𝓁 -1))-approximation for every fixed 𝓁 ∈ ℕ.
Cite as

Yann Disser, Svenja M. Griesbach, Max Klimm, and Annette Lutz. Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{disser_et_al:LIPIcs.ESA.2024.47,
  author =	{Disser, Yann and Griesbach, Svenja M. and Klimm, Max and Lutz, Annette},
  title =	{{Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{47:1--47:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.47},
  URN =		{urn:nbn:de:0030-drops-211188},
  doi =		{10.4230/LIPIcs.ESA.2024.47},
  annote =	{Keywords: incremental optimization, competitive analysis, prize-collecting Steiner-tree}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.62
Optimizing Throughput and Makespan of Queuing Systems by Information Design

Authors: Svenja M. Griesbach, Max Klimm, Philipp Warode, and Theresa Ziemke

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
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 offsets where the latter depend on a realized state, and the number of states is assumed to be constant. A continuum of flow particles (agents) arrives at the system at a constant rate. A system operator knows the realization of the state 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 state, and decide on which link they use. Inflow into a link exceeding the link’s capacity builds up in a queue that increases the cost (total travel time) on the link. Dynamic inflow rates are in a Bayesian dynamic equilibrium when the expected cost along all links with positive inflow is equal at every point in time and not larger than the expected cost of any unused link. 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]. The public signaling scheme maximizing the throughput may involve irrational numbers. We provide an additive polynomial time approximation scheme (PTAS) that approximates the optimal throughput by an arbitrary additive constant ε > 0. The algorithm solves a Lagrangian 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 the optimal signals. It uses a different cell decomposition technique together with a piecewise 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.
Cite as

Svenja M. Griesbach, Max Klimm, Philipp Warode, and Theresa Ziemke. Optimizing Throughput and Makespan of Queuing Systems by Information Design. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 62:1-62:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{griesbach_et_al:LIPIcs.ESA.2024.62,
  author =	{Griesbach, Svenja M. and Klimm, Max and Warode, Philipp and Ziemke, Theresa},
  title =	{{Optimizing Throughput and Makespan of Queuing Systems by Information Design}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{62:1--62:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.62},
  URN =		{urn:nbn:de:0030-drops-211336},
  doi =		{10.4230/LIPIcs.ESA.2024.62},
  annote =	{Keywords: Information Design, Dynamic Flows, Public Signals, Convex Envelope}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.54
Improved Approximation Algorithms for the Expanding Search Problem

Authors: Svenja M. Griesbach, Felix Hommelsheim, Max Klimm, and Kevin Schewior

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
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+ε)-approximation for any ε > 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.
Cite as

Svenja M. Griesbach, Felix Hommelsheim, Max Klimm, and Kevin Schewior. Improved Approximation Algorithms for the Expanding Search Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{griesbach_et_al:LIPIcs.ESA.2023.54,
  author =	{Griesbach, Svenja M. and Hommelsheim, Felix and Klimm, Max and Schewior, Kevin},
  title =	{{Improved Approximation Algorithms for the Expanding Search Problem}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{54:1--54:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.54},
  URN =		{urn:nbn:de:0030-drops-187073},
  doi =		{10.4230/LIPIcs.ESA.2023.54},
  annote =	{Keywords: Approximation Algorithm, Expanding Search, Search Problem, Graph Exploration, Traveling Repairperson Problem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.16
Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages

Authors: Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
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.
Cite as

Michael A. Bekos, Giordano Da Lozzo, Svenja M. Griesbach, Martin Gronemann, Fabrizio Montecchiani, and Chrysanthi Raftopoulou. Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.SoCG.2020.16,
  author =	{Bekos, Michael A. and Da Lozzo, Giordano and Griesbach, Svenja M. and Gronemann, Martin and Montecchiani, Fabrizio and Raftopoulou, Chrysanthi},
  title =	{{Book Embeddings of Nonplanar Graphs with Small Faces in Few Pages}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.16},
  URN =		{urn:nbn:de:0030-drops-121749},
  doi =		{10.4230/LIPIcs.SoCG.2020.16},
  annote =	{Keywords: Book embeddings, Book thickness, Nonplanar graphs, Planar skeleton}
}
  • Refine by Type
  • 7 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 2 2024
  • 1 2023
  • 1 2020

  • Refine by Author
  • 4 Griesbach, Svenja M.
  • 3 Klimm, Max
  • 2 Disser, Yann
  • 1 Bekos, Michael A.
  • 1 Bhaskar, Umang
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Combinatorial algorithms
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Online algorithms
  • Show More...

  • Refine by Keyword
  • 2 competitive analysis
  • 1 1-Planar
  • 1 Approximation Algorithm
  • 1 Approximation Algorithms
  • 1 Book embeddings
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact