Trade-offs between selection complexity and performance when searching the plane without communication

DOI10.1145/2611462.2611463zbMath1321.68480arXiv1405.1688MaRDI QIDQ2943625

Christoph Lenzen, Calvin Newport, Tsvetomira Radeva, Nancy A. Lynch

Publication date: 3 September 2015

Published in: Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.1688

zbMATH Keywords

Markov chains; search algorithms; distributed algorithms; mobile agents; biology-inspired algorithms

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W15: Distributed algorithms

Related Items

ANTS on a Plane, Exploration of High-Dimensional Grids by Finite Automata, How many ants does it take to find the food?, Evacuating from \(\ell_p\) unit disks in the wireless model (extended abstract), Evacuating equilateral triangles and squares in the face-to-face model, The ANTS problem, Searching without communicating: tradeoffs between performance and selection complexity, Evacuating from \(\ell_p\) unit disks in the wireless model, Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract), Evacuating an Equilateral Triangle in the Face-to-Face Model