Informatics 14 - Associate Professorship of Theoretical Computer Science - Research output

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

1 Scopus citations

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

4 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

24 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

48 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

12 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

11 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

44 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

45 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

2011

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

2003

A practical algorithm for constructing oblivious routing schemes

Bieńkowski, M., Korzeniowski, M. & Räcke, H., 2003, p. 1-13. 13 p.

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

31 Scopus citations

Informatics 14 - Associate Professorship of Theoretical Computer Science

Research output

Search results