Memoryless routing in convex subdivisions: random walks are optimal (Q419369): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(7 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Q175421 / rank | |||
Property / author | |||
Property / author: Luc P. Devroye / rank | |||
Normal rank | |||
Property / review text | |||
A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex \(t\) for a packet currently located at vertex \(v\) is made based only on the coordinates of \(v, t\), and the neighborhood \(N(v)\) of \(v\). In this paper, the authors study the limitations of such algorithms. In particular, it is shown that, for any (randomized) memoryless routing algorithm \(\mathcal A\), there exists a convex subdivision on which \(\mathcal A\) takes \(\Omega(n^2)\) expected time to route a message between some pair of vertices. Since this lower bound is matched by a random walk, this result implies that the geometric information available in convex subdivisions is not helpful for this class of routing algorithms. The current paper also shows the existence of triangulations for which the Random-Compass algorithm proposed by \textit{P. Bose} et al. in [Int. J. Comput. Geom. Appl. 12, No. 4, 283--295 (2002; Zbl 1152.68478)] and by \textit{P. Bose} and \textit{P. Morin} [SIAM J. Comput. 33, No. 4, 937--951 (2004; Zbl 1061.65014)] requires \(2^{\Omega(n)}\) time to route between some pair of vertices. | |||
Property / review text: A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex \(t\) for a packet currently located at vertex \(v\) is made based only on the coordinates of \(v, t\), and the neighborhood \(N(v)\) of \(v\). In this paper, the authors study the limitations of such algorithms. In particular, it is shown that, for any (randomized) memoryless routing algorithm \(\mathcal A\), there exists a convex subdivision on which \(\mathcal A\) takes \(\Omega(n^2)\) expected time to route a message between some pair of vertices. Since this lower bound is matched by a random walk, this result implies that the geometric information available in convex subdivisions is not helpful for this class of routing algorithms. The current paper also shows the existence of triangulations for which the Random-Compass algorithm proposed by \textit{P. Bose} et al. in [Int. J. Comput. Geom. Appl. 12, No. 4, 283--295 (2002; Zbl 1152.68478)] and by \textit{P. Bose} and \textit{P. Morin} [SIAM J. Comput. 33, No. 4, 937--951 (2004; Zbl 1061.65014)] requires \(2^{\Omega(n)}\) time to route between some pair of vertices. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65D18 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6036378 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
geometric routing | |||
Property / zbMATH Keywords: geometric routing / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
lower bounds | |||
Property / zbMATH Keywords: lower bounds / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
memoryless routing algorithm | |||
Property / zbMATH Keywords: memoryless routing algorithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
convex subdivision scheme | |||
Property / zbMATH Keywords: convex subdivision scheme / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
random walk | |||
Property / zbMATH Keywords: random walk / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
random-compass algorithm | |||
Property / zbMATH Keywords: random-compass algorithm / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Sonia Pérez-Díaz / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2122684646 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0911.2484 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ONLINE ROUTING IN CONVEX SUBDIVISIONS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Online Routing in Triangulations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Random walks on random trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4856179 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4361347 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Undirected ST-connectivity in log-space / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 06:27, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Memoryless routing in convex subdivisions: random walks are optimal |
scientific article |
Statements
Memoryless routing in convex subdivisions: random walks are optimal (English)
0 references
18 May 2012
0 references
A memoryless routing algorithm is one in which the decision about the next edge on the route to a vertex \(t\) for a packet currently located at vertex \(v\) is made based only on the coordinates of \(v, t\), and the neighborhood \(N(v)\) of \(v\). In this paper, the authors study the limitations of such algorithms. In particular, it is shown that, for any (randomized) memoryless routing algorithm \(\mathcal A\), there exists a convex subdivision on which \(\mathcal A\) takes \(\Omega(n^2)\) expected time to route a message between some pair of vertices. Since this lower bound is matched by a random walk, this result implies that the geometric information available in convex subdivisions is not helpful for this class of routing algorithms. The current paper also shows the existence of triangulations for which the Random-Compass algorithm proposed by \textit{P. Bose} et al. in [Int. J. Comput. Geom. Appl. 12, No. 4, 283--295 (2002; Zbl 1152.68478)] and by \textit{P. Bose} and \textit{P. Morin} [SIAM J. Comput. 33, No. 4, 937--951 (2004; Zbl 1061.65014)] requires \(2^{\Omega(n)}\) time to route between some pair of vertices.
0 references
geometric routing
0 references
lower bounds
0 references
memoryless routing algorithm
0 references
convex subdivision scheme
0 references
random walk
0 references
random-compass algorithm
0 references