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:








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:




Note, Abstract, ©


(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},
ADDRESS = {Hersonissos, Crete, Greece},
MONTH = {July},
ISBN = {1-58113-349-9},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Berthold Voecking
Created
03/17/2002 05:16:11 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
02/14/2005 09:44:07 PM
08.04.2002 13:43:10
08.04.2002 13:35:36
22.03.2002 13:26:14
17/03/2002 17:28:46
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section