2026-07-23T16:36:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24533 2025-10-01T14:50:50Z ddc:004 open_access

From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation Grossmann, Ernestine Reinstädtler, Henrik Rotenberg, Eva Schulz, Christian van der Hoog, Ivor Vlieghe, Juliette Dynamic graphs out-orientation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ernestine Grossmann and Henrik Reinstädtler and Eva Rotenberg and Christian Schulz and Ivor van der Hoog and Juliette Vlieghe 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.65 urn:nbn:de:0030-drops-245331 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.65 eng https://creativecommons.org/licenses/by/4.0/legalcode