Can I read An Efficient Noisy Binary Search in Graphs via Median Approximation on EtoBox?

An Efficient Noisy Binary Search in Graphs via Median Approximation by Dereniowski, Dariusz; Łukasiewicz, Aleksander; Uznański, Przemysław is a scholarly article available to read on EtoBox.

What is An Efficient Noisy Binary Search in Graphs via Median Approximation about?

Consider a generalization of the classical binary search problem in linearly sorted data to the graph-theoretic setting. The goal is to design an adaptive query algorithm, called a strategy, that identifies an initially unknown target vertex in a graph by asking queries. Each query is conducted as follows: the strategy selects a vertex $q$ and receives a reply $v$: if $q$ is the target, then $v=q$, and if $q$ is not the target, then $v$ is a neighbor of $q$ that lies on a shortest path to the target. Furthermore, there is a noise parameter $0\leq p<\frac{1}{2}$, which means that each reply can be incorrect with probability $p$. The optimization criterion to be minimized is the overall number of queries asked by the strategy, called the query complexity. The query complexity is well understood to be $O(\varepsilon^{-2}\log n)$ for general graphs, where $n$ is the order of the graph and $\varepsilon=\frac{1}{2}-p$. However, implementing such a strategy is computationally expensive, with each query requiring possibly $O(n^2)$ operations. In this work we propose two efficient strategies that keep the optimal query complexity. The first strategy achieves the overall complexity of $O(\va

Author

Dereniowski, Dariusz; Łukasiewicz, Aleksander; Uznański, Przemysław

Published

2020

Language

EN