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):

Cooper, Joshua
Doerr, Benjamin
Spencer, Joel
Tardos, Gábor

dblp
dblp
dblp
dblp

Not MPG Author(s):

Cooper, Joshua
Spencer, Joel
Tardos, Gábor

Editor(s):

Raman, Rajeev
Sedgewick, Robert
Stallmann, Matthias F.

dblp
dblp
dblp

Not MPII Editor(s):

Raman, Rajeev
Sedgewick, Robert
Stallmann, Matthias F.

BibTeX cite key*:

DoerrANALCO06

Title, Booktitle

Title*:

Deterministic Random Walks

Booktitle*:

Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments and the Third Workshop on Analytic Algorithmics and Combinatorics (ALENEX'06 / ANALCO'06)

Event, URLs

URL of the conference:


URL for downloading the paper:

http://www.siam.org/meetings/analco06/proceedings06/017jcooper.pdf

Event Address*:

Miami, FL, USA

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

9 March 2007

Event End Date:

9 March 2007

Publisher

Name*:

SIAM

URL:


Address*:

Philadelphia, PA, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

185-197

Year*:

2006

VG Wort Pages:

23

ISBN/ISSN:

0898716101

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

Jim Propp’s P-machine, also known as ‘rotor router model’ is a simple deterministic process that simulates random walk on a graph. Instead of distributing chips
to randomly chosen neighbors, it serves the neighbors in a fixed order.
We investigate how well this process simulates a random walk. For the graph being the infinite path, we show that, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant c1, which is approximately 2.29. For intervals of length L, this improves to a difference of O(log L) (instead of 2.29L), for the L2 average of a contiguous set of intervals even to O(√log L). It seems plausible that similar results hold for higher-dimensional grids Zd instead of the path Z.

HyperLinks / References / URLs:

http://www.siam.org/meetings/analco06/proceedings06/proceedings06.php



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DoerrANALCO06,
AUTHOR = {Cooper, Joshua and Doerr, Benjamin and Spencer, Joel and Tardos, G{\'a}bor},
EDITOR = {Raman, Rajeev and Sedgewick, Robert and Stallmann, Matthias F.},
TITLE = {Deterministic Random Walks},
BOOKTITLE = {Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments and the Third Workshop on Analytic Algorithmics and Combinatorics (ALENEX'06 / ANALCO'06)},
PUBLISHER = {SIAM},
YEAR = {2006},
PAGES = {185--197},
ADDRESS = {Miami, FL, USA},
ISBN = {0898716101},
}


Entry last modified by Christine Kiesel, 05/02/2007
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)
Mathias Bader
Created
03/09/2007 11:54:51 AM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Christine Kiesel
Uwe Brahm
Mathias Bader
Christine Kiesel
Christine Kiesel
Edit Dates
02.05.2007 18:09:09
2007-04-26 18:52:02
13.03.2007 11:21:25
12.03.2007 13:37:55
12.03.2007 13:36:19
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section