Hard-potato routing

Costas Busch, Maurice Herlihy, Rogert Wattenhofer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations


We present the first hot-potato routing algorithm for the n x n mesh whose running time on any quot;hardquot; (i.e., Ω(n)) "many-to-one" batch routing problem is, with high probability, within a polylogarithmic factor of optimal. For any instance I of a batch routing problem, there exists a well-known lower bound LBI based on maximum path length and maximum congestion. If LBI is Ω(n), our algorithm solves I with high probability in time O(LBI·log3 n). The algorithm is distributed and greedy, and it makes use of a new routing technique based on multi-bend paths, a departure from paths using a constant number of bends used in prior hot-potato algorithms.

Original languageEnglish (US)
Title of host publicationProceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Number of pages8
StatePublished - 2000
Externally publishedYes
Event32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, United States
Duration: May 21 2000May 23 2000

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Conference32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Country/TerritoryUnited States
CityPortland, OR

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Hard-potato routing'. Together they form a unique fingerprint.

Cite this