Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Vöcking, Berthold dblp
 Editor(s):
 BibTeX cite key*: Voecking2001b

 Title, Booktitle
 Title*: Almost Optimal Permutation Routing on Hypercubes Booktitle*: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC-01)

 Event, URLs
 URL of the conference: URL for downloading the paper: http://portal.acm.org/citation.cfm?id=380752.380848&coll=portal&dl=ACM&type=series&idx=SERIES396&part=series&WantType=Proceedings&title=Annual%20ACM%20Symposium%20on%20Theory%20of%20Computing&CFID=2148683&CFTOKEN=8528073#FullText Event Address*: Hersonissos, Crete, Greece Language: English Event Date* (no longer used): July, 6-8, 2001 Organization: ACM Event Start Date: 6 July 2001 Event End Date: 8 July 2001

 Publisher
 Name*: ACM URL: Address*: New York, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: July Pages: 530-539 Year*: 2001 VG Wort Pages: ISBN/ISSN: 1-58113-349-9 Sequence Number: DOI:

 (LaTeX) Abstract: This paper deals with permutation routing on hypercube networks in the store-and-forward model. We introduce the first (on-line and off-line) algorithms routing any permutation on the $d$-dimensional hypercube in $d+o(d)$ steps. The best previously known results were $2d+o(d)$ (oblivious on-line) and $2d-3$ (off-line). In particular, we present \begin{itemize} \item a randomized, oblivious on-line algorithm with routing time $d + O(d / \log d)$, \item a matching lower bound of $d + \Omega(d / \log d)$ for (randomized) oblivious on-line routing, and \item a deterministic, off-line algorithm with routing time $d+O(\sqrt{d \log d})$. \end{itemize} Previous algorithms lose a factor of two mainly because packets are first sent to intermediate destinations in order to resolve congestion. As a consequence, the maximum path length becomes $2d - o(d)$. Our algorithms use intermediate destinations as well, but we introduce a simple, elegant trick ensuring that the routing paths are not stretched too much. In fact, we achieve small congestion using paths of length at most $d$. The main focus of our work, however, lies on the scheduling aspect. On one hand, we investigate well-known and practical scheduling policies for on-line routing, namely {\em Farthest-to-Go\/} and {\em Nearest-to-Origin}. On the other hand, we present a new off-line scheduling scheme that is based on frugal colorings of multigraphs. This scheme might be of interest for other sparse scheduling problems, too. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: Expert Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Voecking2001b,
AUTHOR = {V{\"o}cking, Berthold},
TITLE = {Almost Optimal Permutation Routing on Hypercubes},
BOOKTITLE = {Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC-01)},
PUBLISHER = {ACM},
YEAR = {2001},
ORGANIZATION = {ACM},
PAGES = {530--539},