Approximation algorithms for optimal decision trees and adaptive TSP problems

DOI10.1287/MOOR.2016.0831zbMATH Open1420.68236arXiv1003.0722OpenAlexW3098194985MaRDI QIDQ5359124FDOQ5359124

Authors: Anupam Gupta, Viswanath Nagarajan, R. Ravi 

Publication date: 22 September 2017

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: We consider the problem of 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 problem by giving a tight $O(logm)$-approximation algorithm. 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 problem, we give the first poly-logarithmic approximation, and show that this algorithm is best possible unless we can improve the approximation guarantees for the well-known group Steiner tree problem.

Full work available at URL: https://arxiv.org/abs/1003.0722

Recommendations

• Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
• Approximating optimal binary decision trees
• Approximating Optimal Binary Decision Trees
• A Constant Approximation Algorithm for the a priori Traveling Salesman Problem
• Approximation algorithms for stochastic \(k\)-TSP

zbMATH Keywords

decision treesstochastic optimizationapproximation algorithmsvehicle routing

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Stochastic programming (90C15) Approximation algorithms (68W25) Transportation, logistics and supply chain management (90B06) Stochastic network models in operations research (90B15)

Cited In (4)

• A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems
• Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
• Forward bounding on pseudo-trees for DCOPs and ADCOPs
• Adaptive submodular ranking and routing

This page was built for publication: Approximation algorithms for optimal decision trees and adaptive TSP problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5359124)