Approximation algorithms for optimal decision trees and adaptive TSP problems

DOI10.1287/MOOR.2016.0831MaRDI QIDQ5359124zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, Viswanath Nagarajan, R. Ravi

Publication date 22 September 2017

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

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

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)

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.

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

Cited in

(4)

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

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)