Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems

Anupam Gupta (), Viswanath Nagarajan () and R. Ravi ()
Additional contact information
Anupam Gupta: Computer Science Department, Carnegie Mellon University, Pittsburgh
Viswanath Nagarajan: Industrial and Operations Engineering Department, University of Michigan
R. Ravi: Tepper School of Business, Carnegie Mellon University

Mathematics of Operations Research, 2017, vol. 42, issue 3, 876-896

Abstract: We consider the problem of constructing optimal decision trees: given a collection of tests that can disambiguate between a set of m possible diseases, each test having a cost, and the a priori likelihood of any particular disease, what is a good adaptive strategy to perform these tests to minimize the expected cost to identify the disease? This problem has been studied in several works, with O (log m )-approximations known in the special cases when either costs or probabilities are uniform. In this paper, we settle the approximability of the general problem by giving a tight O (log m )-approximation algorithm. We also consider a substantial generalization, the adaptive traveling salesman problem. Given an underlying metric space, a random subset S of vertices is drawn from a known distribution, but S is initially unknown—we get information about whether any vertex is in S only when it is visited. What is a good adaptive strategy to visit all vertices in the random subset S while minimizing the expected distance traveled? This problem has applications in routing message ferries in ad hoc networks and also models switching costs between tests in the optimal decision tree problem. We give a polylogarithmic approximation algorithm for adaptive TSP, which is nearly best possible due to a connection to the well-known group Steiner tree problem. Finally, we consider the related adaptive traveling repairman problem, where the goal is to compute an adaptive tour minimizing the expected sum of arrival times of vertices in the random subset S ; we obtain a polylogarithmic approximation algorithm for this problem as well.

Keywords: approximation algorithms; stochastic optimization; decision trees; vehicle routing (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0831 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:3:p:876-896

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().