Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems

1 Introduction

• The paper frames Adaptive TSP through routing applications where the demand subset is unknown until locations are visited, including sensor collection and disaster assessment.Source: §1 · pp. 1–3
• Earlier decision-tree algorithms could have an Ω(m) guarantee when probabilities and costs were exponential, leaving the general O(logm) algorithm as an open question.Source: §1 · p. 2

1.1 Our Results and Techniques

• O(logm) approximates optimal decision trees with arbitrary test costs and probabilities, matching the known Ω(logm) hardness.Source: §1 · p. 2, §1.1 · p. 3
• There is an O(log^2 n log m)-approximation algorithm for the adaptive Traveling Salesman Problem, where n is the number of vertices and m is the number of scenarios in the demand distribution.Source: §1.1 · p. 3
• The Adaptive TSP algorithm first identifies the realized scenario, using a partial-latency group Steiner approach that is greedy with respect to probability and scenario count.It resolves challenges including exponentially small probabilities and charges its cost against an optimal decision tree.Source: §1.1 · p. 3
• O(log^2 n logm) approximates Adaptive Traveling Repairman, whose objective is expected total arrival time rather than completing a tour.Unlike Adaptive TSP, it cannot first isolate the scenario because a long isolation tour may harm arrival times.Source: §1.1 · p. 4

1.2 Other Related Work

• Adaptive covering problems can have a large adaptivity gap, while universal and a priori TSP reveal the demand set all at once rather than gradually.Source: §1.2 · p. 4

• A decision tree queries vertices and branches on whether demand is present; its expected cost weights each scenario’s path cost by its probability.Source: §2 · p. 5
• The model uses a finite symmetric metric satisfying the triangle inequality, with an explicitly specified distribution whose support size m may affect runtime and performance.Explicit support allows arbitrarily correlated demands; with black-box access, no o(n)-approximation is possible using polynomially many samples.Source: §2 · p. 5
• Adaptive TSP must visit every demanded vertex, whereas Isolation only needs to identify the realized scenario; an approximation for Isolation yields one for Adaptive TSP.Source: §2 · pp. 5–6
• Optimal Decision Tree is exactly Isolation on a weighted star metric, with tests represented by leaves and scenario demands determined by their positive-test sets.Source: §2 · p. 6
• The algorithms use group Steiner variants: Group Steiner Orienteering maximizes covered-group profit under a tour-length bound, while LPGST minimizes weighted arrival-time latency while covering a target number of groups.LPGST’s bicriteria guarantee is used because the problem is harder to approximate than group Steiner tree and admits a better bicriteria bound.Source: §2 · pp. 6–7

3 Approximation Algorithm for the Isolation Problem

• A (4,γ)-bicriteria approximation for GSO yields an O(γ · log m)-approximation for Isolation.Source: §3 · p. 7

3.1 Algorithm for Isolation using LPGST

• A (ρ,4)-bicriteria LPGST approximation yields an O(ρ · log m)-approximation for Isolation.The algorithm repeatedly partitions the candidate scenarios so each part has at most 7/8 of the current set, recursing for O(log m) iterations; each iteration has expected travel at most 2ρ times the sub-instance optimum.Source: §3.1 · pp. 8–12

3.2 Algorithm for LPGST using GSO

• A (4,γ)-bicriteria GSO approximation yields an (O(γ),4)-bicriteria LPGST approximation.The algorithm guesses a tour-length scale, repeatedly applies GSO, concatenates the resulting tours, and returns the lowest-latency solution covering at least h/4 groups.Source: §3.2 · pp. 12–13
• The tour τ has length Θ(γ)·D* and latency O(γ)·Lat*, while σ has length O(γ)·D*.The algorithm concatenates τ and σ to form its LPGST solution.Source: §3.2 · pp. 13–14
• A (4,γ)-bicriteria GSO algorithm gives an O(γ)-approximation for minimum latency group Steiner; using the stated GSO guarantee yields O(log^2 n).Any α-approximation for latency group Steiner gives an O(α·log g)-approximation for group Steiner tree, so improving the latency-group-Steiner bound would improve the standard group Steiner tree bound.Source: §3.2 · pp. 14–15

4 Optimal Decision Tree Problem

• A weighted-star Group Steiner Orienteering instance is equivalent to maximizing a monotone submodular coverage function under a knapsack constraint.Selecting a leaf covers the groups containing it, and the leaf costs consume half the tour-length budget.Source: §4 · p. 16
• O(logm)-approximation for optimal decision trees follows by reducing the problem to Isolation on weighted star metrics.For each disease, the corresponding scenario demands the test leaves whose outcomes are consistent with that disease.Source: §4 · pp. 15–16
• O(logm)-approximation algorithms extend to optimal decision trees with multiway test outcomes, via their reduction to Isolation on weighted star metrics.Each test is represented by a star leaf with cost-derived distance; multiway outcomes use zero-distance copies of each test vertex.Source: §4 · p. 16

5 Adaptive Traveling Salesman Problem

• The algorithm first identifies the realized scenario, returns to the root, then traverses a 3/2-approximate TSP tour of that scenario's demand vertices.The expected TSP tour cost over scenarios is a lower bound on the optimal Adaptive TSP value.Source: §5 · pp. 16–17
• O(log^2 n logm)-approximation for Adaptive TSP follows by combining the Group Steiner Orienteering bicriteria algorithm with the reduction through Isolation.An α-approximation for Isolation yields an (α + 3/2)-approximation for Adaptive TSP; the section uses α = O(log^2 n logm).Source: §5 · p. 17

5.1 Algorithm for Group Steiner Orienteering

• A (4,O(log^2 n))-bicriteria approximation for Group Steiner Orienteering returns a tour of length O(log^2 n)·B with at least one quarter of the optimal profit of a length-B tour.Here n is the number of vertices in the metric.Source: §5.1 · p. 17
• The Group Steiner Orienteering algorithm greedily adds root tours by profit-to-length ratio, using residual profits for uncovered groups.It first restricts the metric to vertices within distance B/2 of the root; this preserves the optimal profit.Source: §5.1 · pp. 17, 19
• The Group Steiner Orienteering rounding step transfers the linear-program solution to a tree metric and rounds capacities to multiples of 1/n^3 before flow-based rounding.Tree embedding increases the budget by O(log n); capacity rounding reduces each cut by at most 1/n^2.Source: §5.1 · p. 18
• A randomized rounding alternative may have the desired length-to-profit ratio in expectation yet fail to find such a solution with reasonable inverse-polynomial probability.The section therefore uses the deterministic rounding result for Group Steiner Orienteering.Source: §5.1 · p. 19

6 Adaptive Traveling Repairman

• Because AdapTRP minimizes arrival-time sums, unlike AdapTSP it cannot first isolate the scenario and then visit its demanded vertices.A star-metric example contrasts an isolation-first strategy with one that visits a frequently demanded vertex early: their expected latencies are respectively Ω(n) and O(√n).Source: §6 · p. 20
• Each iteration uses latency group Steiner to eliminate a constant fraction of candidate scenarios, yielding O(log m) iterations and an O(log^2 n log m) overall approximation.The expected latency incurred in each iteration is bounded using an O(log^2 n)-approximation for latency group Steiner.Source: §6 · pp. 21, 23, 24
• The partitioning step divides vertices into those occurring in more than half the candidate scenarios and those occurring in at most half, then encodes scenario groups in a latency group Steiner instance.For each scenario, the main group includes its low-frequency demanded vertices and high-frequency vertices it does not demand.Source: §6 · p. 21
• O(log^2 n log m) is the approximation guarantee for AdapTRP on general metrics.On tree metrics, the algorithm achieves O(log n log m), leaving a logarithmic gap between the stated upper and lower bounds; moving to general metrics costs another logarithmic factor.Source: §6 · p. 24

7 Concluding Remarks

• The paper gives an O(log m)-approximation for optimal decision trees, asymptotically matching the known hardness.The algorithm covers arbitrary test costs and probabilities; the same ratio holds for tests with non-binary outcomes.Source: §7 · p. 24
• For AdapTSP, the paper gives an O(log^2 n log m)-approximation, and any asymptotic improvement would improve the approximation guarantee for group Steiner tree..Source: §7 · p. 24
• The paper also gives an O(log^2 n log m)-approximation for adaptive traveling repairman, while closing the upper-lower-bound gap remains open..Source: §7 · p. 24

A Hardness of Approximation for AdapTSP

• If an α-approximation algorithm exists for AdapTSP, then group Steiner tree has an (α + o(1))-approximation; consequently, AdapTSP is Ω(log^(2−ε) n)-hard to approximate even on tree metrics.The instance has g+1 scenarios: S_i := X_i ∪ {s} for i ∈ [g], and S_{g+1} := {s}.Source: A Hardness of Approximation for AdapTSP · p. 27
• For the stated AdapTSP instance with root r and L ≫2n·maxu,v d(u,v), its optimal value Opt′ satisfies (1−o(1))·Opt ≤ Opt′ ≤ Opt+1.Source: A Hardness of Approximation for AdapTSP · p. 27
• The proof compares the tour under the scenario containing only the copied root with tours under scenarios that also contain a group.If that tour misses a group, the corresponding group scenario cannot be distinguished from the root-only scenario.Source: A Hardness of Approximation for AdapTSP · p. 27