Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems

We consider the problemof constructing optimal decision trees: given a collection of tests which can disambiguate between a set of m possible diseases, each test having a cost, and the a-priori likelihood of the patient having any particular disease, what is a good adaptive strategy to perform these tests to minimize the expected cost to identify the disease? We settle the approximability of this problemby giving a tight O(logm)-approximation algorithm. The optimal decision tree problemwas known to be Ω(logm)-hard to approximate, and previously o(logm)-approximations were known only under either uniform costs or uniform probabilities. We also consider a more substantial generalization, the Adaptive TSP problem. Given an underlying metric space, a random subset S of cities is drawn from a known distribution, but S is initially unknown to us—we get information about whether any city is in S only when we visit the city in question. What is a good adaptive way of visiting all the cities in the random subset S while minimizing the expected distance traveled? For this adaptive TSP problem, we give the first polylogarithmic approximation, and show that this algorithm is best possible unless we can improve the approximation guarantees for the well-known group Steiner tree problem. We also give an approximation algorithm with the same guarantee for the adaptive traveling repairman problem.