博碩士論文查詢聯邦系統首頁 聯絡信箱 關於我們 加入我們

本論文已被瀏覽 40 次, [ 造訪詳細資料與全文 ] 40 次,[ 回到前頁查詢結果 ] [ 重新搜尋 ]

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

作者:Christoph Lenzen, Calvin Newport, Nancy Ann Lynch, Tsvetomira T. Radeva,
出版單位:Association for Computing Machinery (ACM)
核准日期:2016-01-15
類型:Article http //purl.org/eprint/type/ConferencePape
權限:Creative Commons Attribution-Noncommercial-Share Alike.http://creativecommons.org/licenses/by-nc-sa/4.0/....

英文摘要

We argue that in the context of biology-inspired problems in computer science, in addition to studying the time complexity of solutions it is also important to study the selection complexity, a measure of how likely a given algorithmic strategy is to arise in nature. In this spirit, we propose a selection complexity metric χ for the ANTS problem [Feinerman et al.]. For algorithm A, we define χ(A) = b + log l, where b is the number of memory bits used by each agent and l bounds the fineness of available probabilities (agents use probabilities of at least 1/2[superscript l]). We consider n agents searching for a target in the plane, within an (unknown) distance D from the origin. We identify log log D as a crucial threshold for our selection complexity metric. We prove a new upper bound that achieves near-optimal speed-up of (D[superscript 2]/n +D) ⋅ 2[superscript O(l)] for χ(A) ≤ 3 log log D + O(1), which is asymptotically optimal if l∈ O(1). By comparison, previous algorithms achieving similar speed-up require χ(A) = Ω(log D). We show that this threshold is tight by proving that if χ(A) < log log D - ω(1), then with high probability the target is not found if each agent performs D[superscript 2-o(1)] moves. This constitutes a sizable gap to the straightforward Ω(D[superscript 2]/n + D) lower bound.

United States. Air Force Office of Scientific Research (Contract FA9550-13-1-0042)

National Science Foundation (U.S.) (Award 0939370-CCF)

National Science Foundation (U.S.) (Award CCF-1217506)

National Science Foundation (U.S.) (Award CCF-AF-0937274)

National Science Foundation (U.S.) (Award CCF 1320279)

Deutsche Forschungsgemeinschaft (Le 3107/1-1)

Ford Motor Company. University Research Program


無相關資訊


無相關資訊

 

計畫贊助者: