Harald Räcke
Harald Räcke
Assistant Professor
University of Warwick
Coventry CV4 7AL
United Kingdom

Phone: +44 24 7657 3784
Fax: +44 24 7657 3024
Ph.D., University of Paderborn, Germany, 2003

Committees

FOCS 2006, SPAA 2007, HiPC 2007, FOCS 2008, STACS 2009, ICALP 2009

Publications

My co-authors:
Micah Adler
Konstantin Andreev
Yossi Azar
Mihai Bădoiu
Marcin Bienkowski
Shuchi Chawla
Edith Cohen
Valentina Damerow
Kedar Dhamdhere
Matthias Englert
Alexander Fanghänel
Amos Fiat
Simon Fischer
Anupam Gupta
Mohammad Hajiaghayi
Prahladh Harsha
Tom Hayes
Haim Kaplan
Thomas Kesselheim
Jeong Han Kim
Bobby Kleinberg
Miroslaw Korzeniowski
Christof Krick
Jens Krokowski
Tom Leighton
F. Meyer auf der Heide
Hari Narayanan
Yuri Rabinovich
J. Radhakrishnan
R. Ravi
Adi Rosén
Christian Scheideler
A. Sidiropoulos
Naveen Sivadasan
Christian Sohler
Berthold Vöcking
Matthias Westermann

2009

  • Matthias Englert and Harald Räcke.
    Oblivious Routing in the L_p-norm.
    In Proc. of the 50th FOCS, 2009.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Alexander Fanghänel, Thomas Kesselheim, Harald Räcke, and Berthold Vöcking.
    Oblivious Interference Scheduling.
    In Proc. of the 28th PODC, 2009.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Harald Räcke and Adi Rosén.
    Approximation Algorithms for Time-Constrained Scheduling on Line Networks.
    In Proc. of the 21st SPAA, 2009.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

2008

  • Harald Räcke.
    Optimal Hierarchical Decompositions for Congestion Minimization in Networks.
    In Proc. of the 40th STOC, pp. 255-264, 2008. Co-Winner of Best Paper Award.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, and Jaikumar Radhakrishnan.
    Minimizing Average Latency in Oblivious Routing.
    In Proc. of the 19th SODA, pp. 200-207, 2008.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

2007

  • Matthias Englert, Harald Räcke, and Matthias Westermann.
    Reordering Buffers for General Metric Spaces.
    In Proc. of the 39th STOC, pp. 556-564, 2007.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

2006

  • Simon Fischer, Berthold Vöcking, and Harald Räcke.
    Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods.
    In Proc. of the 38th STOC, pp. 653-662, 2006.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Anupam Gupta, Mohammad Taghi Hajiaghayi, and Harald Räcke.
    Oblivious Network Design.
    In Proc. of the 17th SODA, pp. 970-979, 2006.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Kedar Dhamdhere, Anupam Gupta, and Harald Räcke.
    Improved Embedding of Graph Metrics into Random Trees.
    In Proc. of the 17th SODA, pp. 61-69, 2006.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton, and Harald Räcke.
    New Lower Bounds for Oblivious Routing in Undirected Graphs.
    In Proc. of the 17th SODA, pp. 918-927, 2006.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

2005

  • Mohammad Taghi Hajiaghayi, Jeong Han Kim, Frank Thomson Leighton, and Harald Räcke.
    Oblivious Routing in Directed Graphs with Random Demands.
    In Proc. of the 37th STOC, pp. 193-201, 2005.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, and Anastasios Sidiropoulos.
    Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces.
    In Proc. of the 16th SODA, pp. 119-128, 2005.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Shuchi Chawla, Anupam Gupta, and Harald Räcke.
    Embeddings of Negative type Metrics and an Improved Approximation to Sparsest Cut.
    In Proc. of the 16th SODA, pp. 102-111, 2005.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton, and Harald Räcke.
    Oblivious Routing on Node-Capacitated and Directed Graphs.
    In Proc. of the 16th SODA, pp. 782-790, 2005.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Harald Räcke and Adi Rosén.
    Distributed Online Call Control on General Networks.
    In Proc. of the 16th SODA, pp. 791-800, 2005.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

2004

  • Konstantin Andreev and Harald Räcke.
    Balanced Graph Partitions.
    In Proc. of the 16th SPAA, pp. 120-124, 2004.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Jens Krokowski, Harald Räcke, Christian Sohler, and Matthias Westermann.
    Reducing State Changes with a Pipeline Buffer.
    In Proc. of the 9th VMV, pp. 217-224, 2004.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

2003

  • Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, and Harald Räcke.
    Optimal Oblivious Routing in Polynomial Time.
    In Proc. of the 35th STOC, pp. 383-388, 2003.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Marcin Bienkowski, Miroslaw Korzeniowski, and Harald Räcke.
    A Practical Algorithm for Constructing Oblivious Routing Schemes.
    In Proc. of the 15th SPAA, pp. 24-33, 2003.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Valentina Damerow, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, and Christian Sohler.
    Smoothed Motion Complexity.
    In Proc. of the 11th ESA, pp. 161-171, 2003.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

2002

  • Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, and Berthold Vöcking.
    Randomized Pursuit-Evasion in Graphs.
    In Proc. of the 29th ICALP, pp. 901-912, 2002.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Harald Räcke, Christian Sohler, and Matthias Westermann.
    Online Scheduling for Sorting Buffers.
    In Proc. of the 10th ESA, pp. 820-832, 2002.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Harald Räcke.
    Minimizing Congestion in General Networks.
    In Proc. of the 43rd FOCS, pp. 43-52, 2002. Co-Winner of Best Paper Award.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

2001

  • Christof Krick, Harald Räcke, and Matthias Westermann.
    Approximation Algorithms for Data Management in Networks.
    In Proc. of the 13th SPAA, pp. 237-246, 2001.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

2000

  • Friedhelm Meyer auf der Heide, Harald Räcke, and Matthias Westermann.
    Data Management in Hierarchical Bus Networks.
    In Proc. of the 12th SPAA, pp. 109-118, 2000.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

1999

  • Christof Krick, Friedhelm Meyer auf der Heide, Harald Räcke, Berthold Vöcking, and Matthias Westermann.
    Data Management in Networks: Experimental Evaluation of a Provably Good Strategy.
    In Proc. of the 11th SPAA, pp. 165-174, 1999.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

 
 

Journals:

  • Shuchi Chawla, Anupam Gupta, and Harald Räcke.
    Embeddings of Negative-type Metrics and an Improved Approximation to Sparsest Cut.
    ACM Transactions on Algorithms, 4(2), 2008.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton, and Harald Räcke.
    Oblivious Routing on Node-Capacitated and Directed Graphs.
    ACM Transactions on Algorithms, 3, 2007.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Konstantin Andreev and Harald Räcke.
    Balanced Graph Partitions.
    Theory of Computing Systems, 39(6):929-939, 2006.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Mohammad Taghi Hajiaghayi and Harald Räcke.
    An O(\sqrt{n})-Approximation Algorithm for Directed Sparsest Cut.
    Information Processing Letters, 97(4):156-160, 2006.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, and Harald Räcke.
    Optimal Oblivious Routing in Polynomial Time.
    Journal of Computer and System Sciences, 69(3):383-394, 2004.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, and Berthold Vöcking.
    Randomized Pursuit-Evasion in Graphs.
    Combinatorics, Probability & Computing, 12(3):225-244, 2003.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Christof Krick, Harald Räcke, and Matthias Westermann.
    Approximation Algorithms for Data Management in Networks.
    Theory of Computing Systems, 36(5):497-519, 2003.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Christof Krick, Friedhelm Meyer auf der Heide, Harald Räcke, Berthold Vöcking, and Matthias Westermann.
    Data Management in Networks: Experimental Evaluation of a Provably Good Strategy.
    Theory of Computing Systems, 35(2):217-245, 2002.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

Theses:

  • Harald Räcke.
    Data Management and Routing in General Networks.
    PhD thesis, Universität Paderborn, 2003.
    abstract: xml - html.   full text: ps - ps.gz - pdf.

  • Harald Räcke.
    Data Management in Hierarchical Networks.
    Diplomarbeit, Universität Paderborn, 1999.

 

Other Technical Writings:

  • Harald Räcke.
    Datenverwaltung und Routing in allgemeinen Netzwerken.
    it - Information Technology, 47(4):232-234, 2005.

  • Harald Räcke.
    Data Management and Routing in General Networks.
    In Dorothea Wagner et al., editors, Ausgezeichnete Informatikdissertationen 2003, pp. 179-187. 2004.
    abstract: xml - html.   full text: ps - ps.gz - pdf.