An Efficient Noisy Binary Search in Graphs via Median Approximation

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

doi:10.1007/978-3-030-79987-8_19

An Efficient Noisy Binary Search in Graphs via Median Approximation

Abstrakt

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 =, 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≤<12 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(ε−2log) for general graphs, where n is the order of the graph and ε=1/2−. However, implementing such a strategy is computationally expensive, with each query requiring possibly O(^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(ε−1log) per a single query. The second strategy is dedicated to graphs of small diameter D and maximum degree Δ and has the average complexity of O(+ε−2Δlog) per query. We point out that we develop an algorithmic tool of graph median approximation that is of independent interest: the median can be efficiently approximated by finding a vertex minimizing the sum of distances to a randomly sampled vertex subset of size O(ε−2log).

Cytowania

3

CrossRef
0

Web of Science
6

Scopus

Autorzy (3)

Dariusz Dereniowski prof. dr hab. inż.
- Wydział Elektroniki, Telekomunikacji i Informatyki
- Politechnika Gdańska
Aleksander Łukasiewicz
- Uniwersytet Wrocławski
Przemysław Uznański
- Uniwersytet Wrocławski

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:

Aktywność konferencyjna

Typ:

publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)

Opublikowano w:

LECTURE NOTES IN COMPUTER SCIENCE nr 12757, strony 265 - 281,
ISSN: 0302-9743

Tytuł wydania:

Combinatorial Algorithms strony 265 - 281

Język:

angielski

Rok wydania:

2021

Opis bibliograficzny:

Dereniowski D., Łukasiewicz A., Uznański P.: An Efficient Noisy Binary Search in Graphs via Median Approximation// Combinatorial Algorithms/ : , 2021, s.265-281

DOI: