Search via Parallel Lévy Walks on Z^2

Link identifier archive #link-archive-thumb-soap-66586
Search via Parallel Lévy Walks on Z^2

Venerdì 4 Giugno alle ore 15:00, Francesco D'Amore (INRIA / Université Côte d'Azur) presenterà il seminario di Logica e Informatica Teorica dal titolo: "Search via Parallel Lévy Walks on Z^2". 

Motivated by the Lévy foraging hypothesis -- the premise that various animal species have adapted to follow Lévy walks to optimize their search efficiency -- we study the parallel hitting time of Lévy walks on the infinite two-dimensional grid. We consider k independent discrete-time Lévy walks, with the same exponent α∈(1,∞), that start from the same node, and analyze the number of steps until the first walk visits a given target at distance ℓ. We show that for any choice of k and ℓ from a large range, there is a unique optimal exponent α_k, ℓ∈(2,3), for which the hitting time is Õ(ℓ^2/k) w.h.p., while modifying the exponent by an ε term increases the hitting time by a polynomial factor, or the walks fail to hit the target almost surely. Based on that, we propose a surprisingly simple and effective parallel search strategy, for the setting where k and ℓ are unknown: The exponent of each Lévy walk is just chosen independently and uniformly at random from the interval (2,3). This strategy achieves optimal search time (modulo polylogarithmic factors) among all possible algorithms (even centralized ones that know k). Our results should be contrasted with a line of previous work showing that the exponent α=2 is optimal for various search problems. In our setting of k parallel walks, we show that the optimal exponent depends on k and ℓ, and that randomizing the choice of the exponents works simultaneously for all k and ℓ.
Joint work with Andrea Clementi, George Giakkoupis, and Emanuele Natale.

Per partecipare al Seminario, cliccare sul seguente Link identifier #identifier__10125-1Link.
Link identifier #identifier__20388-1Link identifier #identifier__121616-2Link identifier #identifier__67811-3Link identifier #identifier__128182-4