2026-07-26T05:32:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3964 2024-03-06T10:34:43Z ddc:004 open_access

Constrained Binary Identification Problem Karbasi, Amin Zadimoghaddam, Morteza Network Tomography Binary Identification Problem Approximation Algorithms Graph Algorithms Tree Search Strategies Entropy We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the "20 questions game" of information theory and is closely related to lossless source compression. If any query is admissible, Huffman coding is optimal with close to H[P] questions on average, the entropy of the prior distribution P over objects. However, in many realistic scenarios, there are constraints on which queries can be asked, and solving the problem optimally is NP-hard. We provide novel polynomial time approximation algorithms where constraints are defined in terms of "graph", general "cost", and "submodular" functions. In particular, we show that under graph constraints, there exists a constant approximation algorithm for locating the target in the set. We then extend our approach for scenarios where the constraints are defined in terms of general cost functions that depend only on the size of the query and provide an approximation algorithm that can find the target within O(log(log n)) gap from the cost of the optimum algorithm. Submodular functions come as a natural generalization of cost functions with decreasing marginals. Under submodular set constraints, we devise an approximation algorithm that can find the target within O(log n) gap from the cost of the optimum algorithm. The proposed algorithms are greedy in a sense that at each step they select a query that most evenly splits the set without violating the underlying constraints. These results can be applied to network tomography, active learning and interactive content search. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amin Karbasi and Morteza Zadimoghaddam 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.550 urn:nbn:de:0030-drops-39647 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.550 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode