From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909672911405056 |
|---|---|
| author | Großmann, Ernestine van der Hoog, Ivor Reinstädtler, Henrik Rotenberg, Eva Schulz, Christian Vlieghe, Juliette |
| author_facet | Großmann, Ernestine van der Hoog, Ivor Reinstädtler, Henrik Rotenberg, Eva Schulz, Christian Vlieghe, Juliette |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16720 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation Großmann, Ernestine van der Hoog, Ivor Reinstädtler, Henrik Rotenberg, Eva Schulz, Christian Vlieghe, Juliette Data Structures and Algorithms 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. |
| title | From Theory to Practice: Engineering Approximation Algorithms for Dynamic Orientation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.16720 |