Searching in trees with monotonic query times
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916105374662656 |
|---|---|
| author | Dereniowski, Dariusz Wrosz, Izajasz |
| author_facet | Dereniowski, Dariusz Wrosz, Izajasz |
| contents | We consider the following generalization of binary search in sorted arrays to tree domains. In each step of the search, an algorithm is querying a vertex $q$, and as a reply, it receives an answer, which either states that $q$ is the desired target, or it gives the neighbor of $q$ that is closer to the target than $q$. A further generalization assumes that a vertex-weight function $ω$ gives the query costs, i.e., the cost of querying $q$ is $ω(q)$. The goal is to find an adaptive search strategy requiring the minimum cost in the worst case. This problem is NP-complete for general weight functions and one of the challenging open questions is whether there exists a polynomial-time constant factor approximation algorithm for an arbitrary tree? In this work, we prove that there exist a constant-factor approximation algorithm for trees with a monotonic cost function, i.e., when the tree has a vertex $v$ such that the weights of the subsequent vertices on the path from $v$ to any leaf give a monotonic (non-increasing or non-decreasing) sequence $S$. This gives a constant factor approximation algorithm for trees with cost functions such that each such sequence $S$ has a fixed number of monotonic segments. Finally, we combine several earlier results to show that the problem is NP-complete when the number of monotonic segments in $S$ is at least $4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_13747 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Searching in trees with monotonic query times Dereniowski, Dariusz Wrosz, Izajasz Data Structures and Algorithms Discrete Mathematics 68R10, 68W25 G.2.2; F.2.2 We consider the following generalization of binary search in sorted arrays to tree domains. In each step of the search, an algorithm is querying a vertex $q$, and as a reply, it receives an answer, which either states that $q$ is the desired target, or it gives the neighbor of $q$ that is closer to the target than $q$. A further generalization assumes that a vertex-weight function $ω$ gives the query costs, i.e., the cost of querying $q$ is $ω(q)$. The goal is to find an adaptive search strategy requiring the minimum cost in the worst case. This problem is NP-complete for general weight functions and one of the challenging open questions is whether there exists a polynomial-time constant factor approximation algorithm for an arbitrary tree? In this work, we prove that there exist a constant-factor approximation algorithm for trees with a monotonic cost function, i.e., when the tree has a vertex $v$ such that the weights of the subsequent vertices on the path from $v$ to any leaf give a monotonic (non-increasing or non-decreasing) sequence $S$. This gives a constant factor approximation algorithm for trees with cost functions such that each such sequence $S$ has a fixed number of monotonic segments. Finally, we combine several earlier results to show that the problem is NP-complete when the number of monotonic segments in $S$ is at least $4$. |
| title | Searching in trees with monotonic query times |
| topic | Data Structures and Algorithms Discrete Mathematics 68R10, 68W25 G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2401.13747 |