Search Results

Documents authored by Grossmann, Ernestine

Artifact
Software
DOI: 10.4230/artifacts.24670
Implementation of our dynamic algorithm for minimum orientation

Authors: Ernestine Grossmann, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Ivor van der Hoog, and Juliette Vlieghe

Abstract
Cite as

Ernestine Grossmann, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Ivor van der Hoog, Juliette Vlieghe. Implementation of our dynamic algorithm for minimum orientation (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24670,
   title = {{Implementation of our dynamic algorithm for minimum orientation}}, 
   author = {Grossmann, Ernestine and Reinst\"{a}dtler, Henrik and Rotenberg, Eva and Schulz, Christian and van der Hoog, Ivor and Vlieghe, Juliette},
   note = {Software, Villum Fonden VIL37507, DFG SCHU 2567/8-1, Marie Skłodowska-Curie 899987, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:0ea52feafca9f6d8ce3ee893686fde2510513e9e;origin=https://github.com/DynGraphLab/DynDeltaApprox;visit=swh:1:snp:d75d11daa88538aaa86297daef487996502d243b;anchor=swh:1:rev:f8c3028a966664ce26b0f32c08de00dec2103127}{\texttt{swh:1:dir:0ea52feafca9f6d8ce3ee893686fde2510513e9e}} (visited on 2025-10-01)},
   url = {https://github.com/DynGraphLab/DynDeltaApprox},
   doi = {10.4230/artifacts.24670},
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.65
From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation

Authors: Ernestine Grossmann, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Ivor van der Hoog, and Juliette Vlieghe

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

Abstract
Dynamic graph algorithms have seen significant theoretical advancements, but practical evaluations often lag behind. This work bridges the gap between theory and practice by engineering and empirically evaluating recently developed approximation algorithms for dynamically maintaining graph orientations. We comprehensively describe the underlying data structures, including efficient bucketing techniques and round-robin updates. Our implementation has a natural parameter λ, which allows for a trade-off between algorithmic efficiency and the quality of the solution. In the extensive experimental evaluation, we demonstrate that our implementation offers a considerable speedup. Using different quality metrics, we show that our implementations are very competitive and can outperform previous methods. Overall, our approach solves more instances than other methods while being up to 112 times faster on instances that are solvable by all methods compared.
Cite as

Ernestine Grossmann, Henrik Reinstädtler, Eva Rotenberg, Christian Schulz, Ivor van der Hoog, and Juliette Vlieghe. From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 65:1-65:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grossmann_et_al:LIPIcs.ESA.2025.65,
  author =	{Grossmann, Ernestine and Reinst\"{a}dtler, Henrik and Rotenberg, Eva and Schulz, Christian and van der Hoog, Ivor and Vlieghe, Juliette},
  title =	{{From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{65:1--65:18},
  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.65},
  URN =		{urn:nbn:de:0030-drops-245331},
  doi =		{10.4230/LIPIcs.ESA.2025.65},
  annote =	{Keywords: Dynamic graphs, out-orientation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.22
Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem

Authors: Ernestine Großmann, Kenneth Langedal, and Christian Schulz

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
The Maximum Weight Independent Set problem is a fundamental NP-hard problem in combinatorial optimization with several real-world applications. Given an undirected vertex-weighted graph, the problem is to find a subset of the vertices with the highest possible weight under the constraint that no two vertices in the set can share an edge. This work presents a new iterated local search heuristic called CHILS (Concurrent Hybrid Iterated Local Search). The implementation of CHILS is specifically designed to handle large graphs of varying densities. CHILS outperforms the current state-of-the-art on commonly used benchmark instances, especially on the largest instances. As an added benefit, CHILS can run in parallel to leverage the power of multicore processors. The general technique used in CHILS is a new concurrent metaheuristic called Concurrent Difference-Core Heuristic that can also be applied to other combinatorial problems.
Cite as

Ernestine Großmann, Kenneth Langedal, and Christian Schulz. Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gromann_et_al:LIPIcs.SEA.2025.22,
  author =	{Gro{\ss}mann, Ernestine and Langedal, Kenneth and Schulz, Christian},
  title =	{{Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.22},
  URN =		{urn:nbn:de:0030-drops-232600},
  doi =		{10.4230/LIPIcs.SEA.2025.22},
  annote =	{Keywords: Randomized Local Search, Heuristics, Maximum Weight Independent Set, Algorithm Engineering, Parallel Computing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.11
Engineering Weighted Connectivity Augmentation Algorithms

Authors: Marcelo Fonseca Faraj, Ernestine Großmann, Felix Joos, Thomas Möller, and Christian Schulz

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
Increasing the connectivity of a graph is a pivotal challenge in robust network design. The weighted connectivity augmentation problem is a common version of the problem that takes link costs into consideration. The problem is then to find a minimum cost subset of a given set of weighted links that increases the connectivity of a graph by one when the links are added to the edge set of the input instance. In this work, we give a first implementation of recently discovered better-than-2 approximations. Furthermore, we propose three new heuristics and one exact approach. These include a greedy algorithm considering link costs and the number of unique cuts covered, an approach based on minimum spanning trees and a local search algorithm that may improve a given solution by swapping links of paths. Our exact approach uses an ILP formulation with efficient cut enumeration as well as a fast initialization routine. We then perform an extensive experimental evaluation which shows that our algorithms are faster and yield the best solutions compared to the current state-of-the-art as well as the recently discovered better-than-2 approximation algorithms. Our novel local search algorithm can improve solution quality even further.
Cite as

Marcelo Fonseca Faraj, Ernestine Großmann, Felix Joos, Thomas Möller, and Christian Schulz. Engineering Weighted Connectivity Augmentation Algorithms. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{faraj_et_al:LIPIcs.SEA.2024.11,
  author =	{Faraj, Marcelo Fonseca and Gro{\ss}mann, Ernestine and Joos, Felix and M\"{o}ller, Thomas and Schulz, Christian},
  title =	{{Engineering Weighted Connectivity Augmentation Algorithms}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.11},
  URN =		{urn:nbn:de:0030-drops-203768},
  doi =		{10.4230/LIPIcs.SEA.2024.11},
  annote =	{Keywords: weighted connectivity augmentation, approximation, heuristic, integer linear program, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.16
Arc-Flags Meet Trip-Based Public Transit Routing

Authors: Ernestine Großmann, Jonas Sauer, Christian Schulz, and Patrick Steil

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
We present Arc-Flag TB, a journey planning algorithm for public transit networks which combines Trip-Based Public Transit Routing (TB) with the Arc-Flags speedup technique. Compared to previous attempts to apply Arc-Flags to public transit networks, which saw limited success, our approach uses stronger pruning rules to reduce the search space. Our experiments show that Arc-Flag TB achieves a speedup of up to two orders of magnitude over TB, offering query times of less than a millisecond even on large countrywide networks. Compared to the state-of-the-art speedup technique Trip-Based Public Transit Routing Using Condensed Search Trees (TB-CST), our algorithm achieves similar query times but requires significantly less additional memory. Other state-of-the-art algorithms which achieve even faster query times, e.g., Public Transit Labeling, require enormous memory usage. In contrast, Arc-Flag TB offers a tradeoff between query performance and memory usage due to the fact that the number of regions in the network partition required by our algorithm is a configurable parameter. We also identify a previously undiscovered issue in the transfer precomputation of TB, which causes both TB-CST and Arc-Flag TB to answer some queries incorrectly. We provide discussion on how to resolve this issue in the future. Currently, Arc-Flag TB answers 1-6% of queries incorrectly, compared to over 20% for TB-CST on some networks.
Cite as

Ernestine Großmann, Jonas Sauer, Christian Schulz, and Patrick Steil. Arc-Flags Meet Trip-Based Public Transit Routing. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gromann_et_al:LIPIcs.SEA.2023.16,
  author =	{Gro{\ss}mann, Ernestine and Sauer, Jonas and Schulz, Christian and Steil, Patrick},
  title =	{{Arc-Flags Meet Trip-Based Public Transit Routing}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.16},
  URN =		{urn:nbn:de:0030-drops-183664},
  doi =		{10.4230/LIPIcs.SEA.2023.16},
  annote =	{Keywords: Public transit routing, graph algorithms, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.26
The PACE 2022 Parameterized Algorithms and Computational Experiments Challenge: Directed Feedback Vertex Set

Authors: Ernestine Großmann, Tobias Heuer, Christian Schulz, and Darren Strash

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
The Parameterized Algorithms and Computational Experiments challenge (PACE) 2022 was devoted to engineer algorithms solving the NP-hard Directed Feedback Vertex Set (DFVS) problem. The DFVS problem is to find a minimum subset X ⊆ V in a given directed graph G = (V,E) such that, when all vertices of X and their adjacent edges are deleted from G, the remainder is acyclic. Overall, the challenge had 90 participants from 26 teams, 12 countries, and 3 continents that submitted their implementations to this year’s competition. In this report, we briefly describe the setup of the challenge, the selection of benchmark instances, as well as the ranking of the participating teams. We also briefly outline the approaches used in the submitted solvers.
Cite as

Ernestine Großmann, Tobias Heuer, Christian Schulz, and Darren Strash. The PACE 2022 Parameterized Algorithms and Computational Experiments Challenge: Directed Feedback Vertex Set. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gromann_et_al:LIPIcs.IPEC.2022.26,
  author =	{Gro{\ss}mann, Ernestine and Heuer, Tobias and Schulz, Christian and Strash, Darren},
  title =	{{The PACE 2022 Parameterized Algorithms and Computational Experiments Challenge: Directed Feedback Vertex Set}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.26},
  URN =		{urn:nbn:de:0030-drops-173826},
  doi =		{10.4230/LIPIcs.IPEC.2022.26},
  annote =	{Keywords: Feedback Vertex Set, Algorithm Engineering, FPT, Kernelization, Heuristics}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact