file.pdf (218.09 kB)

Download file# Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems

journal contribution

posted on 01.08.2008, 00:00 by Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, Ramamoorthi RaviRamamoorthi RaviWe 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.