Harald Räcke

View Scopus Profile

Harald Räcke

Prof. Dr.

20012024

Research activity per year

Search results

  • 2024

    Electrical Flows for Polylogarithmic Competitive Oblivious Routing

    Goranci, G., Henzinger, M., Räcke, H., Sachdeva, S. & Sricharan, A. R., Jan 2024, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024. Guruswami, V. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 55. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 287).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

  • Expander Hierarchies for Normalized Cuts on Graphs

    Hanauer, K., Henzinger, M., Münk, R., Räcke, H. & Vötsch, M., 25 Aug 2024, KDD 2024 - Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, p. 1016-1027 12 p. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access

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

    Racke, H., Schmid, S. & Vintan, R., 2024, IEEE INFOCOM 2024 - IEEE Conference on Computer Communications. Institute of Electrical and Electronics Engineers Inc., p. 1930-1939 10 p. (Proceedings - IEEE INFOCOM).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

  • 2023

    Dynamic Maintenance of Monotone Dynamic Programs and Applications

    Henzinger, M., Neumann, S., Räcke, H. & Schmid, S., 1 Mar 2023, 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023. Berenbrink, P., Bouyer, P., Dawar, A. & Kante, M. M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 36. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 254).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    2 Scopus citations

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

    Räcke, H., Schmid, S. & Zabrodin, R., 17 Jun 2023, SPAA 2023 - Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, p. 403-413 11 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
  • 2022

    ALMOST TIGHT BOUNDS FOR REORDERING BUFFER MANAGEMENT

    Adamaszek, A., Czumaj, A., Englert, M. & Racke, H., 2022, In: SIAM Journal on Computing. 51, 3, p. 701-722 22 p.

    Research output: Contribution to journal › Article › peer-review

    Open Access

  • Approximate Dynamic Balanced Graph Partitioning

    Räcke, H., Schmid, S. & Zabrodin, R., 11 Jul 2022, SPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, p. 401-409 9 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    3 Scopus citations

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

    Haeupler, B., Räcke, H. & Ghaffari, M., 6 Sep 2022, STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Leonardi, S. & Gupta, A. (eds.). Association for Computing Machinery, p. 1325-1338 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    17 Scopus citations
  • 2021

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

    Munk, R., Rost, M., Racke, H. & Schmid, S., 21 Jun 2021, 2021 IFIP Networking Conference, IFIP Networking 2021. Institute of Electrical and Electronics Engineers Inc., 9472197. (2021 IFIP Networking Conference, IFIP Networking 2021).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
    2 Scopus citations

  • The expander hierarchy and its applications to dynamic graph algorithms

    Goranci, G., Räcke, H., Saranurak, T. & Tan, Z., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). Association for Computing Machinery, p. 2212-2228 17 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    37 Scopus citations

  • Tight bounds for online graph partitioning

    Henzinger, M., Neumann, S., Räcke, H. & Schmid, S., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). Association for Computing Machinery, p. 2799-2818 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    10 Scopus citations
  • 2020

    Compact oblivious routing in weighted graphs

    Czerner, P. & Räcke, H., 1 Aug 2020, 28th Annual European Symposium on Algorithms, ESA 2020. Grandoni, F., Herman, G. & Sanders, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 36. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 173).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    1 Scopus citations
  • 2019

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

    Sidiropoulos, A., Badoiu, M., Dhamdhere, K., Gupta, A., Indyk, P., Rabinovich, Y., Racke, H. & Ravi, A. R., 2019, In: SIAM Journal on Discrete Mathematics. 33, 1, p. 454-473 20 p.

    Research output: Contribution to journal › Article › peer-review

    2 Scopus citations

  • Compact oblivious routing

    Räcke, H. & Schmid, S., Sep 2019, 27th Annual European Symposium on Algorithms, ESA 2019. Bender, M. A., Svensson, O. & Herman, G. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 75. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 144).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    5 Scopus citations

  • Polylogarithmic guarantees for generalized reordering buffer management

    Englert, M., Racke, H. & Stotz, R., Nov 2019, Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE Computer Society, p. 38-59 22 p. 8948649. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2019-November).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
  • 2018

    An O(log k)-competitive algorithm for generalized caching

    Adamaszek, A., Czumaj, A., Englert, M. & Räcke, H., 2018, In: ACM Transactions on Algorithms. 15, 1, 6.

    Research output: Contribution to journal › Article › peer-review

    Open Access
    10 Scopus citations

  • Trees for vertex cuts, hypergraph cuts and minimum hypergraph bisection

    Räcke, H., Schwartz, R. & Stotz, R., 11 Jul 2018, SPAA 2018 - Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, p. 23-32 10 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    1 Scopus citations
  • 2017

    Reordering buffer management with a logarithmic guarantee in general metric spaces

    Kohler, M. & Räcke, H., 1 Jul 2017, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. Muscholl, A., Indyk, P., Kuhn, F. & Chatzigiannakis, I. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 33. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 80).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    2 Scopus citations

  • Reordering buffers with logarithmic diameter dependency for trees

    Englert, M. & Racke, H., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 1224-1234 11 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
    8 Scopus citations

  • Vertex sparsification in trees

    Goranci, G. & Räcke, H., 2017, Approximation and Online Algorithms - 14th International Workshop, WAOA 2016, Revised Selected Papers. Mastrolilli, M. & Jansen, K. (eds.). Springer Verlag, p. 103-115 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10138 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
    7 Scopus citations
  • 2016

    Improved approximation algorithms for balanced partitioning problems

    Räcke, H. & Stotz, R., 1 Feb 2016, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016. Vollmer, H. & Ollinger, N. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 58. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 47).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    3 Scopus citations

  • Online weighted degree-bounded Steiner networks via novel online mixed packing/covering

    Dehghani, S., Ehsani, S., Hajiaghayi, M., Liaghat, V., Räcke, H. & Seddighin, S., 1 Aug 2016, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. Rabani, Y., Chatzigiannakis, I., Sangiorgi, D. & Mitzenmacher, M. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 42. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 55).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    3 Scopus citations
  • 2014

    Computing cut-based hierarchical decompositions in almost linear time

    Räcke, H., Shah, C. & Täubig, H., 2014, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, p. 227-238 12 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    39 Scopus citations

  • Improved guarantees for tree cut sparsifiers

    Räcke, H. & Shah, C., 2014, Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings. Springer Verlag, p. 774-785 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8737 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    6 Scopus citations

  • Online stochastic reordering buffer scheduling

    Esfandiari, H., Hajiaghayi, M., Khani, M. R., Liaghat, V., Mahini, H. & Räcke, H., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 465-476 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    4 Scopus citations

  • Vertex sparsifiers: New results from old techniques

    Englert, M., Gupta, A., Krauthgamer, R., R̈acke, H., Talgam-Cohen, I. & Talwar, K., 2014, In: SIAM Journal on Computing. 43, 4, p. 1239-1262 24 p.

    Research output: Contribution to journal › Article › peer-review

    Open Access
    42 Scopus citations
  • 2012

    An O(log k)-competitive algorithm for generalized caching

    Adamaszek, A., Czumaj, A., Englert, M. & Räcke, H., 2012, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Association for Computing Machinery, p. 1681-1689 9 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
    25 Scopus citations

  • Optimal online buffer scheduling for block devices

    Adamaszek, A., Czumaj, A., Englert, M. & Räcke, H., 2012, STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing. p. 589-598 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    7 Scopus citations

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

    Damerow, V., Manthey, B., Heide, F. M. A. D., Racke, H., Scheideler, C., Sohler, C. & Tantau, T., Jul 2012, In: ACM Transactions on Algorithms. 8, 3, 30.

    Research output: Contribution to journal › Article › peer-review

    Open Access
    5 Scopus citations
  • 2011

    Almost tight bounds for reordering buffer management

    Adamaszek, A., Czumaj, A., Englert, M. & Räcke, H., 2011, STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 607-616 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
    26 Scopus citations

  • Approximation Algorithms for Time-Constrained Scheduling on Line Networks

    Räcke, H. & Rosén, A., Nov 2011, In: Theory of Computing Systems. 49, 4, p. 834-856 23 p.

    Research output: Contribution to journal › Article › peer-review

    2 Scopus citations
  • 2010

    Fast convergence to wardrop equilibria by adaptive sampling methods

    Fischer, S., Räcke, H. & Vöcking, B., 2010, In: SIAM Journal on Computing. 39, 8, p. 3700-3735 36 p.

    Research output: Contribution to journal › Article › peer-review

    31 Scopus citations

  • Vertex sparsifiers: New results from old techniques

    Englert, M., Gupta, A., Krauthgamer, R., Räcke, H., Talgam-Cohen, I. & Talwar, K., 2010, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Proceedings. p. 152-165 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6302 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
    20 Scopus citations
  • 2009

    Approximation algorithms for time-constrained scheduling on line networks

    Räcke, H. & Rosén, A., 2009, SPAA'09 - Proceedings of the 21st Annual Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery (ACM), p. 337-346 10 p. 1584071. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    6 Scopus citations

  • Oblivious interference scheduling

    Fanghänel, A., Kesselheim, T., Räcke, H. & Vöcking, B., 2009, PODC'09 - Proceedings of the 2009 ACM Symposium on Principles of Distributed Computing. p. 220-229 10 p. 1582752. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    80 Scopus citations

  • Oblivious routing for the Lp-norm

    Englert, M. & Räcke, H., 2009, Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009. p. 32-40 9 p. 5438649. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    16 Scopus citations

  • Survey on oblivious routing strategies

    Räcke, H., 2009, Mathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Proceedings. p. 419-429 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5635 LNCS).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    30 Scopus citations
  • 2008

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

    Chawla, S., Gupta, A. & Räcke, H., 1 May 2008, In: ACM Transactions on Algorithms. 4, 2, 22.

    Research output: Contribution to journal › Article › peer-review

    Open Access
    20 Scopus citations

  • Minimizing average latency in oblivious routing

    Harsha, P., Hayes, T. P., Narayanan, H., Radhakrishnan, J. & Rácke, H., 2008, Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 200-207 8 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    19 Scopus citations

  • Optimal hierarchical decompositions for congestion minimization in networks

    Räcke, H., 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 255-263 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    225 Scopus citations
  • 2007

    Oblivious routing on node-capacitated and directed graphs

    Hajiaghayi, M. T., Kleinberg, R. D., Räcke, H. & Leighton, T., 1 Nov 2007, In: ACM Transactions on Algorithms. 3, 4, 1290688.

    Research output: Contribution to journal › Article › peer-review

    14 Scopus citations

  • Reordering buffers for general metric spaces

    Englert, M., Räcke, H. & Westermann, M., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 556-564 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    Open Access
    15 Scopus citations
  • 2006

    An O(√n-approximation algorithm for directed sparsest cut

    Hajiaghayi, M. T. & Räcke, H., 28 Feb 2006, In: Information Processing Letters. 97, 4, p. 156-160 5 p.

    Research output: Contribution to journal › Article › peer-review

    17 Scopus citations

  • Balanced graph partitioning

    Andreev, K. & Räcke, H., Nov 2006, In: Theory of Computing Systems. 39, 6, p. 929-939 11 p.

    Research output: Contribution to journal › Article › peer-review

    261 Scopus citations

  • Fast convergence to wardrop equilibria by adaptive sampling methods

    Fischer, S., Räcke, H. & Vöcking, B., 2006, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), p. 653-662 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 2006).

    Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

    69 Scopus citations

  • Improved embeddings of graph metrics into random trees

    Dhamdhere, K., Gupta, A. & Räcke, H., 2006, p. 61-69. 9 p.

    Research output: Contribution to conference › Paper › peer-review

    7 Scopus citations

  • New lower bounds for oblivious routing in undirected graphs

    Hajiaghayi, M. T., Kleinberg, R. D., Leighton, T. & Räcke, H., 2006, p. 918-927. 10 p.

    Research output: Contribution to conference › Paper › peer-review

    10 Scopus citations

  • Oblivious network design

    Gupta, A., Hajiaghayi, M. T. & Räcke, H., 2006, p. 970-979. 10 p.

    Research output: Contribution to conference › Paper › peer-review

    71 Scopus citations
  • 2005

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

    Bǎdoiu, M., Dhamdhere, K., Gupta, A., Rabinovich, Y., Räcke, H., Ravi, R. & Sidiropoulos, A., 2005, p. 119-128. 10 p.

    Research output: Contribution to conference › Paper › peer-review

    61 Scopus citations

  • Datenverwaltung und Routing in allgemeinen Netzwerken

    Translated title of the contribution: Data management and routing in general networksRäcke, H., 1 Apr 2005, In: IT - Information Technology. 47, 4, p. 232-234 3 p.

    Research output: Contribution to journal › Article › peer-review