Harald Räcke

CoRR, November, 2025

Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model.

[BibT_eX]

[DOI]

Ruslan Zabrodin

Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, 2025

Incremental Approximate Maximum Flow via Residual Graph Sparsification.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Efficient Contractions of Dynamic Graphs - With Applications.

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual European Symposium on Algorithms, 2025

2024

XCut/XCut v1.0.0.

[BibT_eX]

[DOI]

Dataset, June, 2024

Expander Hierarchies for Normalized Cuts on Graphs.

[BibT_eX]

[DOI]

Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2024

Electrical Flows for Polylogarithmic Competitive Oblivious Routing.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Fast Algorithms for Loop-Free Network Updates using Linear Programming and Local Search.

[BibT_eX]

[DOI]

Radu Vintan

Proceedings of the IEEE INFOCOM 2024, 2024

2023

Dynamic Maintenance of Monotone Dynamic Programs and Applications.

[BibT_eX]

[DOI]

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Polylog-Competitive Algorithms for Dynamic Balanced Graph Partitioning for Ring Demands.

[BibT_eX]

[DOI]

Ruslan Zabrodin

Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

2022

Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality.

[BibT_eX]

[DOI]

Bernhard Haeupler

Mohsen Ghaffari

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Approximate Dynamic Balanced Graph Partitioning.

[BibT_eX]

[DOI]

Ruslan Zabrodin

Proceedings of the SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11, 2022

2021

Tight Bounds for Online Graph Partitioning.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms.

[BibT_eX]

[DOI]

Gramoz Goranci

Thatchaphol Saranurak

Zihan Tan

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

It's Good to Relax: Fast Profit Approximation for Virtual Networks with Latency Constraints.

[BibT_eX]

[DOI]

Proceedings of the IFIP Networking Conference, 2021

Online Balanced Repartitioning of Dynamic Communication Patterns in Polynomial Time.

[BibT_eX]

[DOI]

Tobias Forner

Proceedings of the 2nd Symposium on Algorithmic Principles of Computer Systems, 2021

2020

Compact Oblivious Routing in Weighted Graphs.

[BibT_eX]

[DOI]

Philipp Czerner

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces.

[BibT_eX]

[DOI]

Anastasios Sidiropoulos

SIAM J. Discret. Math., 2019

Polylogarithmic Guarantees for Generalized Reordering Buffer Management.

[BibT_eX]

[DOI]

Richard Stotz

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Compact Oblivious Routing.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Trees for Vertex Cuts, Hypergraph Cuts and Minimum Hypergraph Bisection.

[BibT_eX]

[DOI]

Roy Schwartz

Richard Stotz

Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

2017

Online Degree-Bounded Steiner Network Design.

[BibT_eX]

[DOI]

Sina Dehghani

Soheil Ehsani

MohammadTaghi Hajiaghayi

Vahid Liaghat

CoRR, 2017

Reordering Buffers with Logarithmic Diameter Dependency for Trees.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces.

[BibT_eX]

[DOI]

Matthias Kohler

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Vertex Sparsification in Trees.

[BibT_eX]

[DOI]

Gramoz Goranci

Proceedings of the Approximation and Online Algorithms - 14th International Workshop, 2016

Improved Approximation Algorithms for Balanced Partitioning Problems.

[BibT_eX]

[DOI]

Richard Stotz

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering.

[BibT_eX]

[DOI]

Sina Dehghani

Soheil Ehsani

Vahid Liaghat

Saeed Seddighin

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2014

Computing Cut-Based Hierarchical Decompositions in Almost Linear Time.

[BibT_eX]

[DOI]

Chintan Shah

Hanjo Täubig

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Online Stochastic Reordering Buffer Scheduling.

[BibT_eX]

[DOI]

Hossein Esfandiari

MohammadTaghi Hajiaghayi

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Improved Guarantees for Tree Cut Sparsifiers.

[BibT_eX]

[DOI]

Chintan Shah

Proceedings of the Algorithms - ESA 2014, 2014

2012

Smoothed analysis of left-to-right maxima with applications.

[BibT_eX]

[DOI]

Valentina Damerow

Bodo Manthey

ACM Trans. Algorithms, 2012

Optimal online buffer scheduling for block devices.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

An <i>O</i>(log <i>k</i>)-competitive algorithm for generalized caching.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Almost tight bounds for reordering buffer management.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

Vertex Sparsifiers: New Results from Old Techniques.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2009

Approximation algorithms for time-constrained scheduling on line networks.

[BibT_eX]

[DOI]

Adi Rosén

Proceedings of the SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2009

Oblivious interference scheduling.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

Oblivious Routing for the Lp-norm.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Survey on Oblivious Routing Strategies.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Theory and Computational Practice, 2009

2008

Optimal hierarchical decompositions for congestion minimization in networks.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Minimizing average latency in oblivious routing.

[BibT_eX]

[DOI]

Jaikumar Radhakrishnan

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007

Reordering buffers for general metric spaces.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

An O(sqrt(n))-approximation algorithm for directed sparsest cut.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2006

Fast convergence to Wardrop equilibria by adaptive sampling methods.

[BibT_eX]

[DOI]

Simon Fischer

Berthold Vöcking

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

New lower bounds for oblivious routing in undirected graphs.

[BibT_eX]

[DOI]

Robert D. Kleinberg

Frank Thomson Leighton

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Oblivious network design.

[BibT_eX]

[DOI]

Anupam Gupta

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Improved embeddings of graph metrics into random trees.

[BibT_eX]

[DOI]

Kedar Dhamdhere

Anupam Gupta

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

Datenverwaltung und Routing in allgemeinen Netzwerken.

[BibT_eX]

[DOI]

it Inf. Technol., 2005

Oblivious routing in directed graphs with random demands.

[BibT_eX]

[DOI]

Jeong Han Kim

Tom Leighton

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Distributed online call control on general networks.

[BibT_eX]

[DOI]

Adi Rosén

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Oblivious routing on node-capacitated and directed graphs.

[BibT_eX]

[DOI]

Robert D. Kleinberg

Tom Leighton

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.

[BibT_eX]

[DOI]

Shuchi Chawla

Anupam Gupta

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Approximation algorithms for low-distortion embeddings into low-dimensional spaces.

[BibT_eX]

[DOI]

Anastasios Sidiropoulos

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Reducing State Changes with a Pipeline Buffer.

[BibT_eX]

Proceedings of the 9th International Fall Workshop on Vision, Modeling, and Visualization, 2004

Balanced graph partitioning.

[BibT_eX]

[DOI]

Konstantin Andreev

Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004

2003

Data management and routing in general networks.

[BibT_eX]

[DOI]

PhD thesis, 2003

Optimal oblivious routing in polynomial time.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A practical algorithm for constructing oblivious routing schemes.

[BibT_eX]

[DOI]

Marcin Bienkowski

Miroslaw Korzeniowski

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Data management and routing in general networks.

[BibT_eX]

[DOI]

Proceedings of the Ausgezeichnete Informatikdissertationen 2003, 2003

Smoothed Motion Complexity.

[BibT_eX]

[DOI]

Valentina Damerow

Christian Scheideler

Christian Sohler

Proceedings of the Algorithms, 2003

2002

Randomized Pursuit-Evasion in Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Minimizing Congestion in General Networks.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

Online Scheduling for Sorting Buffers.

[BibT_eX]

[DOI]

Christian Sohler

Proceedings of the Algorithms, 2002

2001

Approximation algorithms for data management in networks.

[BibT_eX]

[DOI]

Christof Krick

Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

2000

Data management in hierarchical bus networks.

[BibT_eX]

[DOI]

Proceedings of the Twelfth annual ACM Symposium on Parallel Algorithms and Architectures, 2000

1999

Data Management in Networks: Experimental Evaluation of a Provably Good Strategy.

[BibT_eX]

[DOI]

Christof Krick

Berthold Vöcking