2024/01/24 by Dariusz Dereniowski, Dereniowski, Dariusz, Izajasz Wrosz +1 · 2 citations
Computer Science · #68R10 #68W25 #Advanced Image and Video Retrieval Techniques #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Machine Learning and Algorithms #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2401.13747
openalex publication_date 2024/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.