Searching without communicating: tradeoffs between performance and selection complexity

DOI10.1007/S00446-016-0283-XMaRDI QIDQ2401119zbMATH OpenOpenAlexFDO

Authors Christoph Lenzen, Calvin Newport, Tsvetomira Radeva, Nancy Lynch

Publication date 31 August 2017

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://hdl.handle.net/1721.1/133426

zbMATH Keywords

Markov chainsdistributed algorithmssearch algorithmsbiology-inspired algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Animal behavior (92D50) Agent technology and artificial intelligence (68T42) Distributed algorithms (68W15) (n)-person games, (n>2) (91A06) Distributed systems (68M14)

Recommendations

• Trade-offs between selection complexity and performance when searching the plane without communication
• The ANTS problem
• Collaborative search on the plane without communication
• Memory lower bounds for randomized collaborative search and implications for biology
• How many ants does it take to find the food?

Cites work

• scientific article; zbMATH DE number 1775412 (Why is no real title available?)
• scientific article; zbMATH DE number 2119714 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• A biological solution to a fundamental distributed computing problem
• Co-evolution of learning complexity and social foraging strategies
• Collaborative search on the plane without communication
• Collective tree exploration
• Exploring Unknown Environments
• Exploring Unknown Undirected Graphs
• Many Random Walks Are Faster Than One
• Memory lower bounds for randomized collaborative search and implications for biology
• On a Problem of Partitions
• Rates of convergence for data augmentation on finite sample spaces
• Solving the ANTS problem with asynchronous finite state machines
• Stone age distributed computing
• Trade-offs between selection complexity and performance when searching the plane without communication
• Tree exploration with logarithmic memory
• Undirected connectivity in log-space

Cited in

(2)

• Trade-offs between selection complexity and performance when searching the plane without communication
• How Do Mobile Agents Benefit from Randomness?

This page was built for publication: Searching without communicating: tradeoffs between performance and selection complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401119)