Approximation Algorithms for Optimal Decision Trees
and Adaptive TSP Problems

arXiv:1003.0722v3 [] 21 Apr 2017

Anupam Gupta∗

Viswanath Nagarajan†

R. Ravi‡

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 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 poly-logarithmic 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
poly-logarithmic approximation algorithm for this problem as well.

1

Introduction

Consider the following two adaptive covering optimization problems:
• Adaptive TSP under stochastic demands (AdapTSP). A traveling salesperson is given a metric space (V, d)
and distinct subsets S1 , S2 , . . . , Sm ⊆ V such that Si appears with probability pi (and ∑i pi = 1). She needs to
serve requests at a random subset S of locations drawn from this distribution. However, she does not know
the identity of the random subset: she can only visit locations, at which time she finds out whether or not
that location is part of the subset S. What adaptive strategy should she use to minimize the expected time
to serve all requests in the random set S?
• Optimal Decision Trees. Given a set of m diseases, there are n binary tests that can be used to disambiguate
between these diseases. If the cost of performing test t ∈ [n] is ct , and we are given the likelihoods {p j } j∈[m]
that a typical patient has the disease j, what (adaptive) strategy should the doctor use for the tests to
minimize the expected cost to identify the disease?
∗ Computer

Science Department, Carnegie Mellon University.
and Operations Engineering Department, University of Michigan.
‡ Tepper School of Business, Carnegie Mellon University.
† Industrial

1

It can be shown that the optimal decision tree problem is a special case of the adaptive TSP problem: a
formal reduction is given in Section 4. In both these problems we want to devise adaptive strategies, which take
into account the revealed information in the queries so far (e.g., locations already visited, or tests already done)
to determine the future course of action. Such an adaptive solution corresponds naturally to a decision tree,
where nodes encode the current “state” of the solution and branches represent observed random outcomes: see
Definition 2 for a formal definition. A simpler class of solutions, that have been useful in some other adaptive
optimization problems, eg. [DGV08, GM09, BGL+ 12], are non-adaptive solutions, which are specified by just
an ordered list of actions. However there are instances for both the above problems where the optimal adaptive
solution costs much less than the optimal non-adaptive solution. Hence it is essential that we find good adaptive
solutions.
The optimal decision tree problem has long been studied, its NP-hardness was shown by Hyafil and Rivest in
1976 [HR77] and many references and applications can be found in [Now11]. There have been a large number of
papers providing algorithms for this problem [GG74,
CPR+ 11, Now11, GB09].
 Lov85,
 KPB99,
 Das04, AH12,

1
The best results yield approximation ratios of O log pmin
and O log(m ccmax
) , where pmin is the minimum
min
non-zero probability and cmax (resp. cmin ) is the maximum (resp. minimum) cost. In the special cases when the
likelihoods {p j } or the costs {ct } are all polynomially bounded in m, these imply an O(log m)-approximation
algorithm. However, there are instances (when probabilities and costs are exponential) demonstrating an Ω(m)
approximation guarantee for all previous algorithms. On the hardness side, an Ω(log m) hardness of approximation (assuming P 6= NP) is known for the optimal decision tree problem [CPR+ 11]. While the existence of
an O(log m)-approximation algorithm for the general optimal decision tree problem has been posed as an open
question, it has not been answered prior to this work.
Optimal decision tree is also a basic problem in average-case active learning [Das04, Now11, GB09]. In this
application, there is a set of n data points, each of which is associated with a + or − label. The labels are initially
unknown. A classifier is a partition of the data points into + and − labels. The true classifier h∗ is the partition
corresponding to the actual data labels. The learner knows beforehand, a “hypothesis class” H consisting of m
classifiers; it is assumed that the true classifier h∗ ∈ H. Furthermore, in the average case model, there is a known
distribution π of h∗ over H. The learner wants to determine h∗ by querying labels at various points. There is a
cost ct associated with querying the label of each data point t. An active learning strategy involves adaptively
querying labels of data points until h∗ ∈ H is identified. The goal is to compute a strategy that minimizes the
expectation (over π) of the cost of all queried points. This is precisely the optimal decision tree problem, with
points being tests and classifiers corresponding to diseases.
Apart from being a natural adaptive routing problem, AdapTSP has many applications in the setting of
message ferrying in ad-hoc networks [ZA03, SRJB03, ZAZ04, ZAZ05, HLS10]. We cite two examples below:
• Data collection in sparse sensor networks (see eg. [SRJB03]). A collection of sensors is spread over a large
geographic area, and one needs to periodically gather sensor data at a base station. Due to the power and
cost overheads of setting up a communication network between the sensors, the data collection is instead
performed by a mobile device (the message ferry) that travels in this space from/to the base station. On
any given day, there is a known distribution D of the subset S of sensors that contain new information: this
might be derived from historical data or domain experts. The routing problem for the ferry then involves
computing a tour (originating from the base station) that visits all sensors in S, at the minimum expected
cost.
• Disaster management (see eg. [ZAZ04]). Consider a post-disaster situation, in which usual communication
networks have broken down. In this case, vehicles can be used in order to visit locations and assess the
damage. Given a distribution of the set of affected locations, the goal here is to route a vehicle that visits
all affected locations as quickly as possible in expectation.

2

In both these applications, due to the absence of a direct communication network, the information at any location
is obtained only when it is visited: this is precisely the AdapTSP problem.

1.1

Our Results and Techniques

In this paper, we settle the approximability of the optimal decision tree problem:
Theorem 1 There is an O(log m)-approximation algorithm for the optimal decision tree problem with arbitrary
test costs and arbitrary probabilities, where m is the number of diseases. The problem admits the same approximation ratio even when the tests have non-binary outcomes.
In fact, this result arises as a special case of the following theorem:
Theorem 2 There is an O(log2 n log m)-approximation algorithm for the adaptive Traveling Salesman Problem,
where n is the number of vertices and m the number of scenarios in the demand distribution.
To solve the AdapTSP problem, we first solve the “isolation problem”, which seeks to identify which of
the m scenarios has materialized. Once we know the scenario we can visit its vertices using any constant-factor
approximation algorithm for TSP. The high-level idea behind our algorithm for the isolation problem is this—
suppose each vertex lies in at most half the scenarios; then if we visit one vertex in each of the m scenarios using
a short tour, which is an instance of the group Steiner tree problem1 , we’d notice at least one of these vertices to
have a demand; this would reduce the number of possible scenarios by at least 50% and we can recursively run
the algorithm on the remaining scenarios. This is an over-simplified view, and there are many details to handle:
we need not visit all scenarios—visiting all but one allows us to infer the last one by exclusion; the expectation
in the objective function means we need to solve a minimum-sum version of group Steiner tree; not all vertices
need lie in less than half the scenarios. Another major issue is that we do not want our performance to depend on
the magnitude of the probabilities, as some of them may be exponentially small. Finally, we need to charge our
cost directly against the optimal decision tree. All these issues can indeed be resolved to obtain Theorem 2.
The algorithm for the isolation problem involves an interesting combination of ideas from the group Steiner [GKR00,
CCGG98] and minimum latency TSP [BCC+ 94, CGRT03, FHR07] problems—it uses a greedy approach that
is greedy with respect to two different criteria, namely the probability measure and the number of scenarios.
This idea is formalized in our algorithm for the partial latency group Steiner (LPGST) problem, which is a key
subroutine for Isolation. While this LPGST problem is harder to approximate than the standard group Steiner
2
tree (see Section
 2), for which O(log n log m) is the best approximation ratio, we show that it admits a better
2
O(log n), 4 bicriteria approximation algorithm. Moreover, even this bicriteria approximation guarantee for
LPGST suffices to obtain an O(log2 n · log m)-approximation algorithm for Isolation.
We also show that both AdapTSP and the isolation problem are Ω(log2−ε n) hard to approximate even on tree
metrics; our results are essentially best possible on such metrics, and we lose an extra logarithmic factor to go
to general metrics, as in the group Steiner tree problem. Moreover, any improvement to the result in Theorem 2
would lead to a similar improvement for the group Steiner tree problem [GKR00, HK03, CP05] which is a
long-standing open question.
For the optimal decision tree problem, we show that we can use a variant of minimum-sum set cover [FLT04]
which is the special case of LPGST on star-metrics. This avoids an O(log2 n) loss in the approximation guarantee,
and hence gives us an O(log m)-approximation algorithm which is best possible [CPR+ 11]. Although this variant
of min-sum set cover is Ω(log m)-hard to approximate (it generalizes set cover as shown in Section 2), we again
give a constant factor bicriteria approximation algorithm, which leads to the O(log m)-approximation for optimal
1 In the group Steiner tree problem [GKR00] the input is a metric (V, d) with root r ∈ V and groups {X ⊆ V } of vertices; the goal is
i
to compute a minimum length tour originating from r that visits at least one vertex of each group.

3

decision tree. Our result further reinforces the close connection between the min-sum set cover problem and the
optimal decision tree problem that was first noticed by [CPR+ 11].
Finally, we consider the related adaptive traveling repairman problem (AdapTRP), which has the same input
as AdapTSP, but the objective is to minimize the expected sum of arrival times at vertices in the materialized
demand set. In this setting, we cannot first isolate the scenario and then visit all its nodes, since a long isolation
tour may negatively impact the arrival times. So AdapTRP (unlike AdapTSP) cannot be reduced to the isolation
problem. However, we show that our techniques for AdapTSP are robust, and can be used to obtain:
Theorem 3 There is an O(log2 n log m)-approximation algorithm for the adaptive Traveling Repairman Problem,
where n is the number of vertices and m the number of scenarios in the demand distribution.
Paper Outline: The results on the isolation problem appear in Section 3. We obtain the improved approximation
algorithm for optimal decision tree in Section 4. The algorithm for the adaptive traveling salesman problem is in
Section 5; Appendix A contains a nearly matching hardness of approximation result. Finally, Section 6 is on the
adaptive traveling repairman problem.

1.2

Other Related Work

The optimal decision tree problem has been studied earlier by many authors, with algorithms and hardness
results being shown by [GG74, HR77, Lov85, KPB99, AH12, Das04, CPR+ 11, CPRS09, GB09]. As mentioned
above, the algorithms in these papers gave O(log m)-approximation ratios only when the probabilities or costs
(or both) are polynomially-bounded. The early papers on optimal decision tree considered tests with only binary
outcomes. More recently, [CPR+ 11] studied the generalization with K ≥ 2 outcomes per test, and gave an
O(log K · log m)-approximation under uniform costs. Subsequently, [CPRS09] improved this bound to O(log m),
again under uniform costs. Later,
[GB09]
gave


 an algorithm
 under arbitrary costs and probabilities, achieving
cmax
1
an approximation ratio of O log pmin or O log(m cmin ) . This is the previous best approximation guarantee;
see also Table 1 in [GB09] for a summary of these results. We note that in terms of the number m of diseases,
the previous best approximation guarantee is only Ω(m). On the other hand, there is an Ω(log m) hardness
of approximation for the optimal decision tree problem [CPR+ 11]. Our O(log m)-approximation algorithm for
arbitrary costs and probabilities solves an open problem from these papers. A crucial aspect of this algorithm is
that it is non greedy. All previous results were based on variants of a greedy algorithm.
There are many results on adaptive optimization dealing with covering problems. E.g., [GV06] considered
the adaptive set-cover problem; they gave an O(log n)-approximation when sets may be chosen multiple times,
and an O(n)-approximation when each set may be chosen at most once. The latter approximation ratio was
improved in [MSW07] to O(log2 n log m), and subsequently to the best-possible O(log n)-approximation ratio
by [LPRY08], also using a greedy algorithm. In recent work [GK11] generalized adaptive set-cover to a setting
termed ‘adaptive submodularity’, and gave many applications. In all these problems, the adaptivity-gap (ratio
between optimal adaptive and non-adaptive solutions) is large, as is the case for the problems considered in this
paper, and so the solutions need to be inherently adaptive.
The AdapTSP problem is related to universal TSP [JLN+ 05, GHR06] and a priori TSP [Jai88, SS08, ST08]
only in spirit—in both the universal and a priori TSP problems, we seek a master tour which is shortcut once
the demand set is known, and the goal is to minimize the worst-case or expected length of the shortcut tour. The
crucial difference is that the demand subset is revealed in toto in these two problems, leaving no possibility of
adaptivity—this is in contrast to the slow revelation of the demand subset that occurs in AdapTSP.

4

2

Preliminaries

We work with a finite metric (V, d) that is given by a set V of n vertices and distance function d : V ×V → R+ .
As usual, we assume that the distance function is symmetric and satisfies the triangle inequality. For any integer
t ≥ 1, we let [t] := {1, 2, . . . ,t}.
Definition 1 (r-tour) Given a metric (V, d) and vertex r ∈ V , an r-tour is any sequence (r = u0 , u1 , · · · , uk = r)
of vertices that begins and ends at r. The length of such an r-tour is ∑ki=1 d(ui , ui−1 ), the total length of all edges
in the tour.
Throughout this paper, we deal with demand distributions over vertex-subsets that are specified explicitly. A
m
demand distribution D is specified by m distinct subsets {Si ⊆ V }m
i=1 having associated probabilities {pi }i=1 such
m
that ∑m
i=1 pi = 1. This means that the realized subset D ⊆ V of demand-vertices will always be one of {Si }i=1 ,
m
where D = Si with probability pi (for all i ∈ [m]). We also refer to the subsets {Si }i=1 as scenarios. The following
definition captures adaptive strategies.
Definition 2 (Decision Tree) A decision tree T in metric (V, d) is a rooted binary tree where each non-leaf node
of T is labeled with a vertex u ∈ V , and its two children uyes and uno correspond to the subtrees taken if there is
demand at u or if there is no demand at u. Thus given any realized demand D ⊆ V , a unique path TD is followed
in T from the root down to a leaf.
Depending on the problem under consideration, there are additional constraints on decision tree T and the expected cost of T is also suitably defined. There is a (problem-specific) cost Ci associated with each scenario
i ∈ [m] that depends on path TSi , and the expected cost of T (under distribution D) is then ∑m
i=1 pi · Ci . For
example in AdapTSP, cost Ci corresponds to the length of path TSi .
Since we deal with explicitly specified demand distributions D, all decision trees we consider will have size
polynomial in m (support size of D) and n (number of vertices).
Adaptive Traveling Salesman This problem consists of a metric (V, d) with root r ∈ V and a demand distribution D over subsets of vertices. The information on whether or not there is demand at a vertex v is obtained
only when that vertex v is visited. The objective is to find an adaptive strategy that minimizes the expected time
to visit all vertices of the realized scenario drawn from D.
We assume that the distribution D is specified explicitly with a support-size of m. This allows us to model demand distributions that are arbitrarily correlated across vertices. We note however that the running time and performance of our algorithm will depend on the support size. The most general setting would be to consider blackbox access to the distribution D: however, as shown in [Nag09], in this setting there is no o(n)-approximation
algorithm for AdapTSP that uses a polynomial number of samples from the distribution. One could also consider
AdapTSP under independent demand distributions. In this case there is a trivial constant-factor approximation
algorithm, that visits all vertices having non-zero probability along an approximately minimum TSP tour; note
that any feasible solution must visit all vertices with non-zero probability as otherwise (due to the independence
assumption) there would be a positive probability of not satisfying a demand.
Definition 3 (Adaptive TSP) The input is a metric (V, d), root r ∈ V and demand distribution D given by m
m
m
distinct subsets {Si ⊆ V }m
i=1 with probabilities {pi }i=1 (where ∑i=1 pi = 1). The goal in AdapTSP is to compute
a decision tree T in metric (V, d) such that:
• the root of T is labeled with the root vertex r, and

5

• for each scenario i ∈ [m], the path TSi followed on input Si contains all vertices in Si .

The objective function is to minimize the expected tour length ∑m
i=1 pi · d(TSi ), where d(TSi ) is the length of the
tour that starts at r, visits the vertices on path TSi in that order, and returns to r.
Isolation Problem This is closely related to AdapTSP. The input is the same as AdapTSP, but the goal is just
to identify the unique scenario that has materialized, and not to visit all the vertices in the realized scenario.
Definition 4 (Isolation Problem) Given metric (V, d), root r and demand distribution D, the goal in Isolation is
to compute a decision tree T in metric (V, d) such that:
• the root of T is labeled with the root vertex r, and
• for each scenario i ∈ [m], the path TSi followed on input Si ends at a distinct leaf-node of T .

The objective is to minimize the expected tour length IsoTime(T ) := ∑m
i=1 pi · d(TSi ), where d(TSi ) is the length of
the r-tour that visits the vertices on path TSi in that order, and returns to r.
The only difference between Isolation and AdapTSP is that the tree path TSi in Isolation need not contain all
vertices of Si , and the paths for different scenarios must end at distinct leaf-nodes. In Section 5 we show that
any approximation algorithm for Isolation leads to an approximation algorithm for AdapTSP. So we focus on
designing algorithms for Isolation.
Optimal Decision Tree This problem involves identifying a random disease from a set of possible diseases
using binary tests.
Definition 5 (Optimal Decision Tree) The input is a set of m diseases with probabilities {pi }m
i=1 that sum to one,
and a collection {T j ⊆ [m]}nj=1 of n binary tests with costs {c j }nj=1 . There is exactly one realized disease: each
disease i ∈ [m] occurs with probability pi . Each test j ∈ [n] returns a positive outcome for subset T j of diseases
and returns a negative outcome for the rest [m] \ T j . The goal in ODT is to compute a decision tree Q where each
internal node is labeled by a test and has two children corresponding to positive/negative test outcomes, such
that for each i ∈ [m] the path Qi followed under disease i ends at a distinct leaf node of Q. The objective is to
minimize the expected cost ∑m
i=1 pi · c(Qi ) where c(Qi ) is the sum of test-costs along path Qi .
Notice that the optimal decision tree problem is exactly Isolation on a weighted star metric. Indeed, given an
instance of ODT, consider a metric (V, d) induced by a weighted star with center r and n leaves corresponding to
c
the tests. For each j ∈ [n], we set d(r, j) = 2j . The demand scenarios are as follows: for each i ∈ [m] scenario i
has demands Si = { j ∈ [n] | i ∈ T j }. It is easy to see that this Isolation instance corresponds exactly to the optimal
decision tree instance. See Section 4 for an example. So any algorithm for Isolation on star-metrics can be used
to solve ODT as well.
Useful Deterministic Problems Recall that the group Steiner tree problem [GKR00, HK03] consists of a
metric (V, d), root r ∈ V and g groups of vertices {Xi ⊆ V }gi=1 , and the goal is to find an r-tour of minimum length
that contains at least one vertex from each group {Xi }gi=1 . Our algorithms for the above stochastic problems rely
on solving some variants of group Steiner tree.
Definition 6 (Group Steiner Orienteering) The input is a metric (V, d), root r ∈ V , g groups of vertices {Xi ⊆
V }gi=1 with associated profits {φi }gi=1 and a length bound B. The goal in GSO is to compute an r-tour of length at
most B that maximizes the total profit of covered groups. A group i ∈ [g] is covered if any vertex from Xi is visited
by the tour.

6

An algorithm for GSO is said to be a (β , γ)-bicriteria approximation algorithm if on any instance of the problem,
it finds an r-tour of length at most γ · B that has profit at least β1 times the optimal (which has length at most B).
Definition 7 (Partial Latency Group Steiner) The input is a metric (V, d), g groups of vertices {Xi ⊆ V }gi=1
with associated weights {wi }gi=1 , root r ∈ V and a target h ≤ g. The goal in LPGST is to compute an r-tour τ
that covers at least h groups and minimizes the weighted sum of arrival times over all groups. The arrival time of
group i ∈ [g] is the length of the shortest prefix of tour τ that contains an Xi -vertex; if the group is not covered,
its arrival time is set to be the entire tour-length. The LPGST objective is termed latency, i.e.
latency(τ)

=

∑i covered wi · arrival timeτ (Xi ) + ∑i uncovered wi · length(τ).

(2.1)

An algorithm for LPGST is said to be a (ρ, σ )-bicriteria approximation algorithm if on any instance of the
problem, it finds an r-tour that covers at least h/σ groups and has latency at most ρ times the optimal (which
covers at least h groups). The reason we focus on a bicriteria approximation for LPGST is that it is harder to
approximate than the group Steiner tree problem (see below) and we can obtain a better bicriteria guarantee for
LPGST.
To see that LPGST is at least as hard to approximate as the group Steiner tree problem, consider an arbitrary
instance of group Steiner tree with metric (V, d), root r ∈ V and g groups {Xi ⊆ V }gi=1 . Construct an instance
of LPGST as follows. The vertices are V 0 = V ∪ {u} where u is a new vertex. Let L := n2 · maxa,b d(a, b).
The distances in metric (V 0 , d 0 ) are: d 0 (a, b) = d(a, b) if a, b ∈ V and d 0 (a, u) = L + d(a, r) if a ∈ V . There are
0
= {u}. The target h = g. The weights are wi = 0 for i ∈ [g]
g0 = g + 1 groups with Xi0 = Xi for i ∈ [g] and Xg+1
and wg+1 = 1. Since the distance from r to u is very large, no approximately optimal LPGST solution will visit u.
So any such LPGST solution covers all the groups {Xi0 }gi=1 and has latency equal to the length of the solution (as
0
group Xg+1
has weight one and all others have weight zero). This reduction also shows that LPGST on weighted
star-metrics (which is used in the ODT algorithm) is at least as hard to approximate as set cover: this is because
when metric (V, d) is a star-metric with center r, so is the new metric (V 0 , d 0 ).2

3

Approximation Algorithm for the Isolation Problem

Recall that an instance of Isolation is specified by a metric (V, d), a root vertex r ∈ V , and m scenarios {Si }m
i=1
with associated probability values {pi }m
.
The
main
result
of
this
section
is:
i=1
Theorem 4 If there is a (4, γ)-bicriteria approximation algorithm for group Steiner orienteering then there is an
O(γ · log m)-approximation algorithm for the isolation problem.
We prove this in two steps. First, in Subsection 3.1 we show that a (ρ, 4)-bicriteria approximation algorithm
for LPGST can be used to obtain an O(ρ · log m)-approximation algorithm for Isolation. Then, in Subsection 3.2
we show that any (4, γ)-bicriteria approximation algorithm for GSO leads to an (O(γ), 4)-bicriteria approximation
algorithm for LPGST.
Note on reading this section: While the results of this section apply to the isolation problem on general
metrics, readers interested in just the optimal decision tree problem need to only consider weighted star metrics
(as discussed after Definition 5). In the ODT case, we have the following simplifications (1) a tour is simply
a sequence of tests, (2) the tour length is the sum of test costs in the sequence, and (3) concatenating tours
corresponds to concatenating test sequences.
2 Recall

that group Steiner tree on star-metrics is equivalent to the set cover problem.

7

3.1

Algorithm for Isolation using LPGST

Recall the definition of Isolation and LPGST from Section 2. Here we will prove:
Theorem 5 If there is a (ρ, 4)-bicriteria approximation algorithm for LPGST then there is an O(ρ · log m)approximation algorithm for Isolation.
We first give a high-level description of our algorithm. The algorithm uses an iterative approach and maintains
a candidate set of scenarios that contains the realized scenario. In each iteration, the algorithm eliminates a
constant fraction of scenarios from the candidate set. So the number of iterations will be bounded by O(log m).
In each iteration we solve a suitable instance of LPGST in order to refine the candidate set of scenarios.
Single iteration of Isolation algorithm As mentioned above, we use LPGST in each iteration of the Isolation
algorithm- we now describe how this is done. At the start of each iteration, our algorithm maintains a candidate
set M ⊆ [m] of scenarios that contains the realized scenario. The probabilities associated with the scenarios
i ∈ M are not the original pi s but their conditional probabilities qi := ∑ pi p j . The algorithm Partition (given as
j∈M
Algorithm 1) uses LPGST to compute an r-tour τ such that after observing the demands on τ, the number of
scenarios consistent with these observations is guaranteed to be a constant factor smaller than |M|.
To get some intuition for this algorithm, consider the simplistic case when there is a vertex u ∈ V located near
the root r such that ≈ 50% of the scenarios in M contain it. Then just visiting vertex u would reduce the number
candidate scenarios by ≈ 50%, irrespective of the observation at u, giving us the desired notion of progress.
However, each vertex may give a very unbalanced partition of M: so we may have to visit multiple vertices
before ensuring that the number of candidate scenarios reduces by a constant factor. Moreover, some vertices
may be too expensive to visit from r: so we need to carefully take the metric into account in choosing the set of
vertices to visit. Addressing these issues is precisely where the LPGST problem comes in.
Algorithm 1 Algorithm Partition( hM, {qi }i∈M i )
1:
2:
3:

4:
5:

let g = |M|. For each v ∈ V , define Fv := {i ∈ M | v ∈ Si }, and Dv :=



Fv
M \ Fv

if |Fv | ≤ g/2
if |Fv | > g/2

for each i ∈ M, set Xi ← {v ∈ V | i ∈ Dv }.
run the (ρ, 4)-bicriteria approximation algorithm for LPGST on the instance with metric (V, d), root r,
groups {Xi }i∈M with weights {qi }i∈M , and target h := g − 1.
let τ := r, v1 , v2 , · · · , vt−1 , r be the r-tour returned.


let {Pk }tk=1 be the partition of M where Pk :=
return tour τ and the partition {Pk }tk=1 .

Dvk \ ∪ j<k Dvj
M \ ∪ j<t Dv j

if 1 ≤ k ≤ t − 1
if k = t

Note that the information at any vertex v corresponds to a bi-partition (Fv , M \ Fv ) of the scenario set M,
with scenarios Fv having demand at v and scenarios M \ Fv having no demand at v. So either the presence of
demand or the absence of demand reduces the number of candidate scenarios by half (and represents progress).
To better handle this asymmetry, Step 1 associates vertex v with subset Dv which is the smaller of {Fv , M \ Fv };
this corresponds to the set of scenarios under which just the observation at v suffices to reduce the number of
candidate scenarios below |M|/2 (and represents progress). In Steps 2 and 3, we view vertex v as covering the
scenarios Dv .
The overall algorithm for Isolation Here we describe how the different iterations are combined to solve
Isolation. The final algorithm IsoAlg (given as Algorithm 2) is described in a recursive manner where each
“iteration” is a new call to IsoAlg. As mentioned earlier, at the start of each iteration, the algorithm maintains a

8

r

Subtrees corresponding to {Pk }4k=1 are constructed recursively.

v1
yes

Dv1 corresponds to the yes branch

no

r

Dv2 and Dv3 correspond to the no branch.

v2
no

yes

P1

r

v3
yes

no

r

P2

r

P4

P3

Figure 3.1: Example of decision tree in single iteration using tour τ = (r, v1 , v2 , v3 , r).
candidate set M ⊆ [m] of scenarios such that the realized scenario lies in M. Upon observing demands along the
tour produced by algorithm Partition, a new set M 0 ⊆ M containing the realized scenario is identified such that
the number of candidate scenarios reduces by a constant factor (specifically |M 0 | ≤ 87 · |M|). Then IsoAlg recurses
on scenarios M 0 , which corresponds to the next iteration. After O(log m) such iterations the realized scenario
would be correctly identified.
Algorithm 2 Algorithm IsoAlghM, {qi }i∈M i
1: If |M| = 1, return this unique scenario as realized.
2: run PartitionhM, {qi }i∈M i
let τ = (r, v1 , v2 , · · · , vt−1 , r) be the r-tour and {Pk }tk=1 be the partition of M returned.
3: let q0k := ∑i∈Pk qi for all k = 1 . . .t.
4: traverse tour τ and return directly to r after visiting the first (if any) vertex vk∗ (for k∗ ∈ [t −1]) that determines
that the realized scenario is in Pk∗ ⊆ M. If there is no such vertex until the end of the tour τ, then set k∗ ← t.
q
5: run IsoAlghPk∗ , { q0 i }i∈Pk∗ i to isolate the realized scenario within the subset Pk∗ .
∗
k

Note that the adaptive Algorithm IsoAlg implicitly defines a decision tree too: indeed, we create a path
(r, v1 , v2 , · · · , vt−1 , vt = r), and hang the subtrees created in the recursive call on each instance hPk , { qq0i }i from the
k
respective node vk . See also Figure 3.1.
Analysis The rest of this subsection analyzes IsoAlg and proves Theorem 5. We first provide an outline of the
proof. It is easy to show that IsoAlg correctly identifies the realized scenario after O(log m) iterations: this is
shown formally in Claim 10. We relate the objective values of the LPGST and Isolation instances in two steps:
Claim 6 shows that LPGST has a smaller optimal value than Isolation, and Claim 8 shows that any approximate
LPGST solution can be used to construct a partial Isolation solution incurring the same cost (in expectation).
Since different iterations of IsoAlg deal with different sub-instances of Isolation, we need to relate the optimal

9

cost of these sub-instances to that of the original instance: this is done in Claim 9.
Recall that the original instance of Isolation is defined on metric (V, d), root r and set {Si }m
i=1 of scenarios
.
IsoAlg
works
with
many
sub-instances
of
the
isolation
problem.
Such
an instance J
with probabilities {pi }m
i=1
pi
is specified by a subset M ⊆ [m] which implicitly defines (conditional) probabilities qi = ∑ p j for all i ∈ M. In
j∈M
other words, J involves identifying the realized scenario conditioned on it being in set M (the metric and root
remain the same as the original instance). Let IsoTime∗ (J ) denote the optimal value of any instance J .
Claim 6 For any instance J = hM, {qi }i∈M i, the optimal value of the LPGST instance considered in Step 3 of
algorithm Partition(J ) is at most IsoTime∗ (J ).
Proof: Let T be an optimal decision tree corresponding to Isolation instance J , and hence IsoTime∗ (J ) =
IsoTime(T ). Note that by definition of the sets {Fv }v∈V , any internal node in T labeled vertex v has its two
children vyes and vno corresponding to the realized scenario being in Fv and M \Fv (respectively); and by definition
of {Dv }v∈V , nodes vyes and vno correspond to the realized scenario being in Dv and M \ Dv (now not necessarily
in that order).
We now define an r-tour σ based on a specific root-leaf path in T . Consider the root-leaf path that at any
node labeled v, moves to the child vyes or vno that corresponds to M \ Dv , until it reaches a leaf-node `. Let
r, u1 , u2 , · · · , u j denote the sequence of vertices in this root-leaf path, and define r-tour σ = hr, u1 , u2 , · · · , u j , ri.
Since T is a feasible decision tree for the isolation instance, there is at most one scenario a ∈ M such that the
path TSa traced in T under demands Sa ends at leaf-node `. In other words, every scenario b ∈ M \ {a} gives rise
to a root-leaf path TSb that diverges from the root-` path. By our definition of the root-` path, the scenarios that
j
j
diverge from it are precisely ∪k=1
Duk , and so ∪k=1
Duk = M \ {a}.
Next, we show that σ is a feasible solution to the LPGST instance in Step 3. By definition of the groups
j
{Xi }i∈M (Step 2 of Algorithm 1), it follows that tour σ covers groups ∪k=1
Duk . So the number of groups covered
is at least |M| − 1 = h, and σ is a feasible LPGST solution.
Finally, we bound the LPGST objective value of σ in terms of the isolation cost IsoTime(T ). To reduce
notation let u0 = r below. The arrival times in tour σ are:
 k
k−1
Dus , for k = 1, · · · , j
∑s=1 d(us−1 , us ) if i ∈ Duk \ ∪s=1
arrival timeσ (Xi ) =
length(σ )
if i = a
k−1
Fix any k = 1, · · · , j. For any scenario i ∈ Duk \ ∪s=1
Dus , the path TSi traced in T contains the prefix labeled
k
r, u1 , · · · , uk of the root-` path; so d(TSi ) ≥ ∑s=1 d(us−1 , us ) = arrival timeσ (Xi ). Moreover, for scenario a which
j
is the only scenario not in ∪k=1
Duk , we have d(TSa ) = length(σ ) = arrival timeσ (Xi ). Now by (2.1), latency(σ ) ≤
q
·
d(T
)
=
IsoTime(T
)
=
IsoTime∗ (J ).

∑i∈M i
Si

If we use a (ρ, 4)-bicriteria approximation algorithm for LPGST, we get the following claim:
Claim 7 For any instance J = hM, {qi }i∈M i, the latency of tour τ returned by Algorithm Partition is at most
ρ · IsoTime∗ (J ). Furthermore, the resulting partition {Pk }tk=1 has each |Pk | ≤ 87 |M| for each k ∈ [t], when
|M| ≥ 2.
Proof: By Claim 6, the optimal value of the LPGST instance in Step 3 of algorithm Partition is at most
IsoTime∗ (J ); now the (ρ, 4)-bicriteria approximation guarantee implies that the latency of the solution tour
τ is at most ρ times that. This proves the first part of the claim.
Consider τ := hr = v0 , v1 , · · · , vt−1 , vt = ri the tour returned by the LPGST algorithm in Step 3 of algorithm
Partition; and {Pk }tk=1 the resulting partition. The (ρ, 4)-bicriteria approximation guarantee implies that the
|M|−1
h
number of groups covered by τ is | ∪t−1
≥ |M|
k=1 Dvk | ≥ 4 =
4
8 (when |M| ≥ 2). By definition of the sets Dv , it

10

holds that |Dv | ≤ |M|/2 for all v ∈ V . Since all but the last part Pt is a subset of some Dv , it holds that |Pk | ≤ |M|
2
for 1 ≤ k ≤ t − 1. Moreover, the set Pt has size |Pt | = |M \ (∪ j<t Dv j )| ≤ 78 |M|. This proves the second part of the
claim.

Of course, we don’t really care about the latency of the tour per se, we care about the expected cost incurred
in isolating the realized scenario. But the two are related (by their very construction), as the following claim
formalizes:
Claim 8 At the end of Step 4 of IsoAlghM, {qi }i∈M i, the realized scenario lies in Pk∗ . The expected distance
traversed in this step is at most 2ρ · IsoTime∗ (hM, {qi }i∈M i).
Proof: Consider the tour τ := hr = v0 , v1 , · · · , vt−1 , vt = ri returned by the Partition algorithm. Recall that visiting
any vertex v reveals whether the scenario lies in Dv , or in M \ Dv . In step 4 of algorithm IsoAlg, we traverse τ and
one of the following happens:
• 1 ≤ k∗ ≤ t − 1. Tour returns directly to r from the first vertex vk (for 1 ≤ k ≤ t − 1) such that the realized
scenario lies in Dvk ; here k = k∗ . Since the scenario did not lie in any earlier Dv j for j < k, the definition of
Pk = Dvk \ (∪ j<k Dv j ) gives us that the realized scenario is indeed in Pk .
• k∗ = t. Tour τ is completely traversed and we return to r. In this case, the realized scenario does not lie in
any of {Dvk | 1 ≤ k ≤ t − 1}, and it is inferred to be in the complement set M \ (∪ j<t Dv j ), which is Pt by
definition.
Hence for k∗ as defined in Step 4 of IsoAlghM, {qi }i∈M i, it follows that Pk∗ contains the realized scenario; this
proves the first part of the claim (and correctness of the algorithm).
For each i ∈ M, let αi denote the arrival time of group Xi in tour τ; recall that this is the length of the shortest
prefix of τ until it visits an Xi -vertex, and is set to the entire tour length if τ does not cover Xi . The construction
of partition {Pk }tk=1 from τ implies that
αi = ∑kj=1 d(v j−1 , v j );

∀i ∈ Pk , ∀1 ≤ k ≤ t,

and hence latency(τ) = ∑i∈M qi · αi .
To bound the expected distance traversed, note the probability that the traversal returns to r from vertex vk
(for 1 ≤ k ≤ t − 1) is exactly ∑i∈Pk qi ; with the remaining ∑i∈Pt qi probability the entire tour τ is traversed. Now,
using symmetry and triangle-inequality of the distance function d, we have d(vk , r) ≤ ∑kj=1 d(v j−1 , v j ) for all
k ∈ [t]. Hence the expected length traversed is at most:
!
!
!
!
t

k

∑ ∑ qi
k=1

i∈Pk

t

· d(vk , r) + ∑ d(v j−1 , v j )

k

≤ 2· ∑

j=1

∑ qi

i∈Pk

k=1

·

∑ d(v j−1 , v j )

j=1

= 2 · ∑ qi · αi ,
i∈M

which is exactly 2 · latency(τ). Finally, by Claim 10, this is at most 2 · ρ · IsoTime∗ (hM, {qi }i∈M i).
Now, the following simple claim captures the “sub-additivity” of IsoTime∗ .



Claim 9 For any instance hM, {qi }i∈M i and any partition {Pk }tk=1 of M,
∑tk=1 q0k · IsoTime∗ (hPk , { q0i }i∈Pk i)
q

k

where q0k = ∑i∈Pk qi for all 1 ≤ k ≤ t.

11

≤

IsoTime∗ (hM, {qi }i∈M i),

(3.2)

Proof: Let T denote the optimal decision tree for the instance J0 := hM, {qi }i∈M i. For each k ∈ [t], consider
instance Jk := hPk , { qq0i }i∈Pk i; a feasible decision tree for instance Jk is obtained by taking the decision tree T
k
and considering only paths to the leaf-nodes labeled by {i ∈ Pk }. Note that this is a feasible solution since T
isolates all scenarios ∪tk=1 Pk . Moreover, the expected cost of such a decision tree for Jk is ∑i∈Pk qq0i · d(TSi ); recall
k
that TSi denotes the tour traced by T under scenario i ∈ Pk . Hence Opt(Jk ) ≤ ∑i∈Pk qq0i · d(TSi ). Summing over all
k
parts k ∈ [t], we get
t

∑ q0k · Opt(Jk )

k=1

t

≤

qi

∑ q0k · ∑ q0 · d(TS )
i

k=1

i∈Pk

k

=

∑ qi · d(TS )
i

=

Opt(J0 ),

(3.3)

i∈M

where the penultimate equality uses the fact that {Pk }tk=1 is a partition of M.
Given the above claims, we can bound the overall expected cost of the algorithm.



Claim 10 The expected length of the decision tree given by IsoAlghM, {qi }i∈M i is at most:
2ρ · log8/7 |M| · IsoTime∗ (hM, {qi }i∈M i).
Proof: We prove this by induction on |M|. The base case of |M| = 1 is trivial, since zero length is traversed. Now
consider |M| ≥ 2. Let instance I0 := hM, {qi }i∈M i. For each k ∈ [t], consider the instance Ik := hPk , { qq0i }i∈Pk i,
k

where q0k = ∑i∈Pk qi . Note that |Pk | ≤ 87 |M| < |M| for all k ∈ [t] by Claim 10 (as |M| ≥ 2). By the inductive
hypothesis, for any k ∈ [t], the expected length of IsoAlg(Ik ) is at most 2ρ · log8/7 |Pk | · IsoTime∗ (Ik ) ≤ 2ρ ·
(log8/7 |M| − 1) · IsoTime∗ (Ik ), since |Pk | ≤ 87 |M|.
By Claim 8, the expected length traversed in Step 4 of IsoAlg(I0 ) is at most 2ρ · IsoTime∗ (I0 ). The probability of recursing on Ik is exactly q0k for each k ∈ [t]. So,
expected length of IsoAlg(I0 ) ≤ 2ρ · IsoTime∗ (I0 ) + ∑tk=1 q0k · (expected length of IsoAlg(Ik ))

≤ 2ρ · IsoTime∗ (I0 ) + ∑tk=1 q0k · 2ρ · (log8/7 |M| − 1) · IsoTime∗ (Ik )

≤ 2ρ · IsoTime∗ (I0 ) + 2ρ · (log8/7 |M| − 1) · IsoTime∗ (I0 )

= 2ρ · log8/7 |M| · IsoTime∗ (I0 )

where the third inequality uses Claim 9.

Claim 10 implies that our algorithm achieves an O(ρ log m)-approximation for Isolation. This completes the
proof of Theorem 5.

3.2

Algorithm for LPGST using GSO

Recall the definitions of LPGST and GSO from Section 2. Here we will prove:
Theorem 11 If there is a (4, γ)-bicriteria approximation algorithm for GSO then there is an (O(γ), 4)-bicriteria
approximation algorithm for LPGST.
We now describe the algorithm for LPGST in Theorem 11. Consider any instance of LPGST with metric
(V, d), root r ∈ V , g groups of vertices {Xi ⊆ V }gi=1 having weights {wi }gi=1 , and target h ≤ g. Let ζ ∗ be an
optimal tour for the given instance of LPGST: let Lat∗ denote the latency and D∗ the length of ζ ∗ . We assume
(without loss of generality) that the minimum non-zero distance in the metric is one. Let parameter a := 54 .
Algorithm 3 is the approximation algorithm for LPGST. The “guess” in the first step means the following. We
run the algorithm for all choices of l and return the solution having minimum latency amongst those that cover at
least h/4 groups. Since 1 < D∗ ≤ n · maxe de , the number of choices for l is at most log (n · maxe de ), and so the
algorithm runs in polynomial time.

12

Algorithm 3 Algorithm for LPGST
1: guess an integer l such that al−1 < D∗ ≤ al .
2: mark all groups as uncovered.
3: for i = 1 . . . l do
4:
run the (β , γ)-bicriteria approximation algorithm for GSO on the instance with groups {Xi }gi=1 , root r,
length bound ai+1 , and profits:

0
for each covered group i ∈ [g]
φi :=
wi for each uncovered group i ∈ [g]
5:
6:
7:
8:
9:
10:
11:
12:

let τ (i) denote the r-tour obtained above.
mark all groups visited by τ (i) as covered.
end for
construct tour τ ← τ (1) ◦ τ (2) ◦ · · · ◦ τ (l) , the concatenation of all the above r-tours.
Extend τ if necessary to ensure that d(τ) ≥ γ · al (this is only needed for the analysis).
run the (β , γ)-bicriteria approximation algorithm for GSO on the instance with groups {Xi }gi=1 , root r, length
bound al , and unit profit for each group, i.e. φi = 1 for all i ∈ [g].
let σ denote the r-tour obtained above.
output tour π := τ ◦ σ as solution to the LPGST instance.

Analysis In order to prove Theorem 11, we will show that the algorithm’s tour covers at least
latency O(γ) · Lat∗ .

h
4

groups and has

Claim 12 The tour τ in Step 9 has length Θ(γ) · D∗ and latency O(γ) · Lat∗ .
Proof: Due to the (β , γ)-bicriteria approximation guarantee of the GSO algorithm used in Step 4, the length
γ
γa3 ∗
of each r-tour τ (i) is at most γ · ai+1 . So the length of τ in Step 8 is at most γ ∑li=1 ai+1 ≤ a−1
al+2 ≤ a−1
D .
∗
∗
Moreover, the increase in Step 9 ensures that d(τ) ≥ γ · D . Thus the length of τ in Step 8 is Θ(γ) · D , which
proves the first part of the claim.
The following proof for bounding the latency is based on techniques from the minimum latency TSP [CGRT03,
FHR07]. Recall the optimal solution ζ ∗ to the LPGST instance, where d(ζ ∗ ) = D∗ ∈ (al−1 , al ]. For each i ∈ [l],
let Ni∗ denote the total weight of groups visited in ζ ∗ by time ai ; note that Nl∗ equals the total weight of the groups
covered by ζ ∗ . Similarly, for each i ∈ [l], let Ni denote the total weight of groups visited in τ (1) · · · τ (i) , i.e. by
iteration i of the algorithm. Set N0 = N0∗ := 0, and W := ∑gi=1 wi the total weight of all groups. We have:
l

latency(τ) ≤

i

l

∑ (Ni − Ni−1 ) · ∑ γa j+1

i=1

j=1

l

=

+ (W − Nl ) · d(τ) ≤ ∑ (Ni − Ni−1 ) ·
i=1

γai+2

∑ ((W − Ni−1 ) − (W − Ni )) · a − 1

i=1

The last inequality uses the bound d(τ) ≤
The latency of the optimal tour ζ ∗ is
Lat∗ ≥
≥

l−1

∗
)
∑ ai−1 (Ni∗ − Ni−1

i=1
l−1

∑ ai−1

i=1

γ
l+2
a−1 a

γai+2
+ (W − Nl ) · d(τ)
a−1

l

+ (W − Nl ) · d(τ) ≤ ∑ (W − Ni ) ·
i=0

γai+3
a−1

=:

T.

from above.

+ (W − Nl∗ ) · D∗


∗
(W − Ni−1
) − (W − Ni∗ ) + (W − Nl∗ ) · al−1

13

≥

1 l
(1 − ) ∑ ai (W − Ni∗ ).
a i=0

Consider any iteration i ∈ [l] of the algorithm in Step 4. Note that the optimal value of the GSO instance
solved in this iteration is at least Ni∗ − Ni−1 : the ai length prefix of tour ζ ∗ corresponds to a feasible solution to
this GSO instance with profit at least Ni∗ − Ni−1 . The GSO algorithm implies that the profit obtained in τ (i) , i.e.
Ni − Ni−1 ≥ 41 · (Ni∗ − Ni−1 ), i.e. W − Ni ≤ 43 · (W − Ni−1 ) + 41 · (W − Ni∗ ). Using this,
(a − 1)

T
γ

l

=

∑ ai+3 · (W − Ni )

i=0

≤
≤

a3 ·W +

≤

1 l i+3
3 l i+3
∗
a
(W
−
N
)
+
∑
∑ a (W − Ni−1 )
i
4 i=1
4 i=1

3 l
a4
· Lat∗ + ∑ ai+3 (W − Ni−1 )
a−1
4 i=1
3a
T
a4
· Lat∗ + · (a − 1)
a−1
4
γ

=

3a l−1 i+3
a4
· Lat∗ +
∑ a (W − Ni )
a−1
4 i=0

4

a
This implies T ≤ γ · (a−1)2 (1−3a/4)
· Lat∗ = O(γ) · Lat∗ since a = 45 . This completes the proof.

Claim 13 The tour σ in Step 10 covers at least

h
4



groups and has length O(γ) · D∗ .

Proof: Since we know that the optimal tour ζ ∗ has length at most al and covers at least h groups, it is a feasible
solution to the GSO instance defined in Step 10. So the GSO algorithm ensures that the tour σ has length at most
γal = O(γ)D∗ and profit (i.e. number of groups) at least h/4.

Lemma 14 Tour π = τ · σ covers at least

h
4

groups and has latency O(γ) · Lat∗ .

Proof: Since π visits all the vertices in σ , Claim 13 implies that π covers at least 4h groups. For each group
i ∈ [g], let αi denote its arrival time under the tour τ after Step 9—recall that the arrival time αi for any group
i that is not covered by τ is set to the length of the tour d(τ). Claim 12 implies that the latency of tour τ,
g
∑i=1 wi · αi = O(γ) · Lat∗ . Observe that for each group i that is covered in τ, its arrival time under tour π = τ · σ
remains αi . For any group j not covered in τ, its arrival time under τ is d(τ) ≥ γ · al (due to Step 9), and its arrival
time under π is d(π) ≤ O(γ) · D∗ = O(1) · d(τ). Hence, the arrival time under π of each group i ∈ [g] is O(1) · αi ,
i.e., at most a constant factor more than its arrival time in τ. Now using Claim 12 completes the proof.

Finally, Lemma 14 directly implies Theorem 11.
Remark: The above approach also leads to an approximation algorithm for the minimum latency group Steiner
problem, which is the special case of LPGST when the target h = g.
Definition 8 (Minimum Latency Group Steiner) The input is a metric (V, d), g groups of vertices {Xi ⊆ V }gi=1
with associated non-negative weights {wi }gi=1 and root r ∈ V . The goal in LGST is to compute an r-tour that
covers all groups with positive weight and minimizes the weighted sum of arrival times of the groups. The arrival
time of group i ∈ [g] is the length of the shortest prefix of the tour that contains a vertex from Xi .
Note that the objective here is to minimize the sum of weighted arrival times where every group has to be visited.
The algorithm for latency group Steiner is in fact simpler than Algorithm 3: we do not need the “guess” l (Step 1)
and we just repeat Step 4 until all groups are covered (instead of stopping after l iterations). A proof identical to
that in Claim 12 gives:
Corollary 15 If there is a (4, γ)-bicriteria approximation algorithm for GSO then there is an O(γ)-approximation
algorithm for the latency group Steiner problem.

14

Combined with the (4, O(log2 n)-bicriteria approximation algorithm for GSO (see Section 5.1) we obtain an
O(log2 n)-approximation algorithm for LGST. It is shown in [Nag09] that any α-approximation algorithm for
LGST can be used to obtain an O(α · log g)-approximation algorithm for group Steiner tree. Thus improving this
O(log2 n)-approximation algorithm for latency group Steiner would also improve the best known bound for the
standard group Steiner tree problem.

4

Optimal Decision Tree Problem

Recall that the optimal decision tree problem consists of a set of diseases with their probabilities (where exactly
one disease occurs) and a set of binary tests with costs, and the goal is to identify the realized disease at minimum
expected cost. In this section we prove Theorem 1.
As noted in Section 2 the optimal decision tree problem (Definition 5) is a special case of Isolation (Definition 4). We recall the reduction for convenience. Given an instance of ODT, consider a metric (V, d) induced
c
by a weighted star with center r and n leaves corresponding to the tests. For each j ∈ [n], we set d(r, j) = 2j .
The demand scenarios are as follows: for each i ∈ [m] scenario i has demands Si = { j ∈ [n] | i ∈ T j }. It is easy
to see that this Isolation instance corresponds exactly to the optimal decision tree instance. Figure 4.2 gives an
example.
Binary tests {A, B, C, D} and diseases {α, β, γ, δ}.
cost :
prob.
0.1

α

4

10

2

6

A

B

C

D

+

+

−

r
1

−

0.1

β

+

+

+

−

0.2

γ

+

−

+

+

0.6

δ

−

−

−

+

3

2

C

D

5

A

Scenario β is {A, B, C} w.p. 0.1.
B

Multiway tests {A, B, C} with l = 3 outcomes. Diseases {α, β, γ, δ}.
cost :
prob.
0.1

α

4

10

2

A

B

C

0

1

0

r
1
2
(C, 0)

0.1

β

1

2

0

0.2

γ

1

2

2

0.6

δ

2

2

1

5
(A, 0)
(A, 1)

(C, 2)
(C, 1)

(A, 2)

Dotted edges have zero length.
(B, 0)
(B, 1)

(B, 2)

Scenario β is {(A, 1), (B, 2), (C, 0)}.

Figure 4.2: Reducing optimal decision tree to Isolation: binary tests (top), multiway tests (bottom).

15

The main observation here is the following:
Theorem 16 There is a (1− 1e )-approximation algorithm for the group Steiner orienteering problem on weighted
star metrics.
Proof: Consider an instance of GSO (Definition 6) on weighted star-metric (V, d) with center r (which is also the
root in GSO) and leaves [n], g groups {Xi ⊆ [n]}gi=1 with profits {φi }gi=1 , and length bound B. If for each j ∈ [n],
we define set Y j := {i ∈ [g] | j ∈ Xi } of cost c j := d(r,2 j) , then solving the GSO instance is the same as computing
a collection K ⊆ [n] of the sets with ∑ j∈K c j ≤ B/2 that maximizes f (K) := ∑{φi | i ∈ ∪ j∈K Y j }. But the latter
problem is precisely an instance of maximizing a monotone submodular function over a knapsack constraint
(∑ j∈K c j ≤ B/2), for which a (1 − 1e )-approximation algorithm is known [Svi04].

Combining this result with Theorem 4, we obtain an O(log m) approximation algorithm for Isolation on
weighted star-metrics and hence ODT. This proves the first part of Theorem 1.
Multiway tests. Our algorithm can be easily extended to the generalization of ODT where tests have multiway
(instead of binary) outcomes. In this setting (when each test has at most l outcomes), any test j ∈ [n] induces
a partition {T jk }lk=1 of [m] into l parts (some of them may be empty), and performing test j determines which
part the realized disease lies in. Note that this problem is also a special case of Isolation. As before, consider a
metric (V, d) induced by a weighted star with center r and n leaves corresponding to the tests. For each j ∈ [n],
c
we set d(r, j) = 2j . Additionally, for each j ∈ [n], introduce l copies of test-vertex j, labeled ( j, 1), · · · , ( j, l),
at zero distance from each other. The demand scenarios are defined naturally: for each i ∈ [m], scenario i has
demands Si = {( j, k) | i ∈ T jk }. See also an example in Figure 4.2. Clearly this Isolation instance is equivalent
to the (multiway) decision tree instance. Since the resulting metric is still a weighted star (we only made vertex
copies), Theorem 16 along with Theorem 4 implies an O(log m)-approximation for the multiway decision tree
problem. This proves the second part of Theorem 1.

5

Adaptive Traveling Salesman Problem

Recall that the adaptive TSP (Definition 3) consists of a metric (V, d) with root r ∈ V and demand distribution D,
and the goal is to visit all demand vertices (drawn from D) using an r-tour of minimum expected cost. We first
show the following simple fact relating this problem to the isolation problem.

Lemma 17 If there is an α-approximation algorithm for Isolation then there is an α + 32 -approximation algorithm for AdapTSP.
Proof: We first claim that any feasible solution T to AdapTSP is also feasible for Isolation. For this it suffices
to show that the paths TSi 6= TS j for any two scenarios i, j ∈ [m] with i 6= j. Suppose (for a contradiction) that
S
paths TSi = TS j = π for some i 6= j. By feasibility of T for AdapTSP, path π contains all vertices in Si S j . Since
S
Si 6= S j , there is some vertex in (Si \ S j ) (S j \ Si ); let u ∈ Si \ S j (the other case is identical). Consider the point
where π is at a node labeled u: then path TSi must take the yes child, whereas path TS j must take the no child. This
contradicts the assumption TSi = TS j = π. Thus any solution to AdapTSP is also feasible for Isolation; moreover
the expected cost remains the same. Hence the optimal value of Isolation is at most that of AdapTSP.
Now, using any α-approximation algorithm for Isolation, we obtain a decision tree T 0 that isolates the realized
scenario and has expected cost α · Opt, where Opt denotes the optimal value of the AdapTSP instance. This
suggests the following feasible solution for AdapTSP:
1. Implement T 0 to determine the realized scenario k ∈ [m], and return to r.

16

2. Traverse a 32 -approximate TSP tour [Chr77] on vertices {r} Sk .
S

From the preceding argument, the expected length in the first phase is at most α · Opt. The expected length in the
S
second phase is at most 32 ∑m
i=1 pi · Tsp(Si ), where Tsp(Si ) denotes the minimum length of a TSP tour on {r} Si .
Note that ∑m
i=1 pi · Tsp(Si ) is a lower bound on the optimal AdapTSP value. So we obtain a solution that has
expected cost at most (α + 23 )Opt, as claimed.

Therefore, it suffices to obtain an approximation algorithm for Isolation. In the next subsection we obtain
a (4, O(log2 n))-bicriteria approximation algorithm for GSO, which combined with Theorem 4 and Lemma 17
yields an O(log2 n · log m)-approximation algorithm for both Isolation and AdapTSP. This would prove Theorem 2.

5.1

Algorithm for Group Steiner Orienteering

Recall the GSO problem (Definition 6). Here we obtain a bicriteria approximation algorithm for GSO.
Theorem 18 There is a (4, O(log2 n))-bicriteria approximation algorithm for GSO, where n is the number of
vertices in the metric. That is, the algorithm’s tour has length O(log2 n) · B and has profit at least 14 times the
optimal profit of a length B tour.
This algorithm is based on a greedy framework that is used in many maximum-coverage problems: the
solution is constructed iteratively where each iteration adds an r-tour that maximizes the ratio of profit to length.
In order to find an r-tour (approximately) maximizing the profit to length ratio, we use a slight modification of
an existing algorithm [CCGG98]; see Theorem 19 below. The final GSO algorithm is then given as Algorithm 5.
Theorem 19 There is a polynomial time algorithm that given any instance of GSO, outputs an r-tour σ having
(σ )
1 Opt
profit-to-length ratio φd(σ
) ≥ α · B . Here φ (σ ) and d(σ ) denote the profit and length (respectively) of tour σ ,

Opt is the optimal value of the GSO instance, B is the length bound in GSO and α = O(log2 n) where n is the
number of vertices in the metric.
Proof: This result essentially follows from [CCGG98], but requires some modifications which we present here
for completeness. We first preprocess the metric to only include vertices within distance B/2 from the root r:
note that since the optimal GSO tour cannot visit any excluded vertex, the optimal profit remains unchanged by
this. To reduce notation, we refer
 to this restricted vertex-set also as V and let |V | = n. We denote the set of all
V
edges in the metric by E = 2 . We assume (without loss of generality) that every group is covered by some
vertex in V ; otherwise the group can be dropped from the GSO instance. By averaging, there is some vertex
u ∈ V covering groups of total profit at least n1 ∑gi=1 φi . If Opt ≤ 4n ∑gi=1 φi then the r-tour that just visits vertex u
Opt
1 g
has profit-to-length ratio at least Opt
4B and is output as the desired tour σ . Below we assume that n ∑i=1 φi < 4 .
We use the following linear programming relaxation LPGSO for GSO:
max
s.t.

g
∑i=1 φi · yi
x(δ (S)) ≥ yi

∑e∈E de · xe ≤ B
0 ≤ yi ≤ 1
xe ≥ 0

(5.4)
∀S ⊆ V : r 6∈ S, Xi ⊆ S; ∀i ∈ [g]
∀i ∈ [g]
∀e ∈ E

It is easy to see that this a valid relaxation of GSO: any feasible GSO solution corresponds to a feasible solution
above where the x, y variables are {0, 1} valued. So the optimal value ∑gi=1 φi · yi ≥ Opt. The algorithm is given

17

as Algorithm 4 and uses the following known results: Theorem 20 shows how to round fractional solutions to
LPGSO on tree metrics and Theorem 21 shows how to transform an LPGSO solution on general metrics to one on
a tree.
Theorem 20 ([CCGG98]) There is a polynomial time algorithm that given any fractional solution (x, y) to
LPGSO on a tree metric where all variables are integral multiples of N1 , finds a subtree A containing r such
∑e∈E de ·xe
that φd(A)
(A) ≤ O(log N) · ∑g φ ·y . Here φ (A) and d(A) denote the profit and length (respectively) of subtree A.
i=1 i

i


Theorem 21 ([FRT04]) There is a polynomial time algorithm that given any metric (V, d) with edges E = V2
and capacity function x : E → R+ , computes a spanning tree T in this metric such that ∑ f ∈T d f ·xT ( f ) ≤ O(log n)·
∑e∈E de · x(e), where
xT ( f ) :=
x(u, v),
∀ f ∈ T.
∑
u,v : f ∈uv path in T

Algorithm 4 Algorithm for GSO maximizing profit-to-length ratio.
1: solve the linear program LPGSO to obtain solution (x, y).
2: run the algorithm from Theorem 21 on metric (V, d) with edge-capacities x to obtain a spanning tree T with
“new capacities” xT on edges of T .
3: round down each xT (e) to an integral multiple of n13 .
4: for each group i ∈ [g], let y0i be the maximum flow from r to group Xi under capacities xT .
5: run the algorithm from Theorem 20 using variables xT and y0 to obtain subtree A.
6: output an Euler tour σ of the subtree A.
By definition of the new edge-capacities xT on edges of T (see Theorem 21) it is clear that the capacity of
each cut under xT is at least as much as under x; i.e. ∑e∈δ (S) xT (e) ≥ ∑e∈δ (S) x(e) for all S ⊆ V . For each group
i ∈ [g], since capacities x support yi units of flow from r to Xi , it follows that the new capacities xT on tree T also
support such a flow. So (xT , y) is a feasible solution to LPGSO on tree T with budget O(log n) · B. In order to
apply the rounding algorithm from [CCGG98] for GSO on trees, we need to ensure the technical condition (see
Theorem 20) that every variable is an integral multiple of N1 for some N = poly(n). This is the reason behind
modifying capacities xT in Step 3. Note that this step reduces the capacity xT (e) of each edge e ∈ T by at most
1
. Since any cut in tree T has at most n edges, the capacity of any cut decreases by at most n12 after Step 3; and
n3
by the max-flow min-cut theorem, the maximum flow value for group Xi is y0i ≥ yi − n12 for each i ∈ [g] (in Step 4).
Furthermore, since all edge capacities are integer multiples of n13 , so are all the flow values y0i s. So (xT , y0 ) is a
feasible solution to LPGSO on tree T (with budget O(log n) · B) that satisfies the condition required in Theorem 20,
with N = n3 . Also note that this rounding down does not change the fractional profits much, since
g

g

∑ φi · y0i

i=1

≥

1

g

∑ φi · yi − n2 ∑ φi

i=1

i=1

≥

3
1 g
3
Opt
Opt
· Opt − 2 ∑ φi ≥ · Opt −
≥
4
n i=1
4
4n
2

where the second last inequality follows from n1 ∑gi=1 φi ≤
implies that subtree A satisfies:
d(A)
φ (A)

≤(T heorem 20)
≤(T heorem 21)

Opt
4

(by the preprocessing). Now applying Theorem 20

∑e∈T de · xT (e)
≤(5.5)
g
∑i=1 φi · y0i
∑ de · x(e)
≤
O(log N log n) · e∈E
Opt
O(log N) ·

18

(5.5)

∑e∈T de · xT (e)
Opt
B
O(log2 n) ·
.
Opt
O(log N) ·

Finally, since we output an Euler tour of A, the theorem follows.



Remark: A simpler approach in Theorem 19 might have been to use the randomized algorithm from [GKR00]
rather than the deterministic algorithm (Theorem 20) from [CCGG98]. This however does not work directly since
[GKR00] only yields a random solution A0 with expected length E[d(A0 )] ≤ O(log n) · ∑e∈E de · xe and expected
profit E[φ (A0 )] ≥ ∑gi=1 φi · yi . While this does guarantee the existence of a solution with length-to-profit ratio at
de ·xe
most O(log n) · ∑∑e∈E
, it may not find such a solution with reasonable (inverse polynomial) probability.
g
φ ·y
i=1 i

i

Algorithm The GSO algorithm first preprocesses the metric to only include vertices within distance B/2 from
the root r: note that the optimal profit remains unchanged by this. The algorithm then follows a standard greedy
approach (see eg. Garg [Gar96]), and is given as Algorithm 5.
Algorithm 5 Algorithm for GSO.
1: initialize r-tour τ ← 0/ and mark all groups as uncovered.
2: while length of τ does not exceed α · B do
3:
set residual profits:

0 for each covered group i ∈ [g]
e
φi :=
φi for each uncovered group i ∈ [g]
4:
5:
6:

run the algorithm from Theorem 19 on the GSO instance with profits φe to obtain r-tour σ .
if d(σ ) ≤ αB then τ 0 ← τ ◦ σ .
if d(σ ) > αB then:
(i)

)
partition tour σ into at most 2 · d(σ
αB paths, each of length at most αB;

(ii)

let σ 0 denote the path containing maximum profit;

(iii)

let hr, σ 0 , ri be the r-tour obtained by connecting both end-vertices of path σ 0 to r.

(iv)

set τ 0 ← τ ∪ hr, σ 0 , ri.

set τ ← τ 0 . Mark all groups visited in τ as covered.
8: end while
9: output the r-tour τ.
7:

Analysis Let Opt denote the optimal profit of the given GSO instance. In the following, let α := O(log2 n)
which comes from Theorem 19. We prove that Algorithm 5 achieves a (4, 2α + 1) bicriteria approximation
guarantee, i.e. solution τ has profit at least Opt/4 and length (2α + 1) · B.
By the description of the algorithm, we iterate as long as the total length of edges in τ is at most αB. Note
that the increase in length of τ in any iteration is at most (α + 1) · B since every vertex is at distance at most B/2
from r. So the final length d(τ) ≤ (2α + 1) · B. This proves the bound on the length.
It now suffices to show that the final subgraph τ gets profit at least Opt
4 . At any iteration, let φ (τ) denote the
profit of the current solution τ, and d(τ) its length. Since d(τ) > αB upon termination, it suffices to show the
following invariant over the iterations of the algorithm:


Opt Opt
φ (τ) ≥ min
,
· d(τ)
(5.6)
4 2αB

19

At the start of the algorithm, inequality (5.6) holds trivially since d(τ) = 0 for τ = 0.
/ Consider any iteration
where φ (τ) < Opt/4 at the beginning: otherwise (5.6) trivially holds for the next iteration. The invariant now
ensures that d(τ) < αB/2 and hence we proceed further with the iteration. Moreover, in Step 4 the optimal value
g ≥ Opt − φ (τ) ≥ 3 · Opt (by considering the optimal tour for
of the “residual” GSO instance with profits φe is Opt
4
g ≤ 2α · B/Opt.
the GSO instance with profits φ ). By Theorem 19, the r-tour σ satisfies d(σ )/φe(σ ) ≤ α · B/Opt
We finish by handling the two possible cases (Steps 5 and 6).
• If d(σ ) ≤ αB, then φ (τ 0 ) = φ (τ) + φe(σ ) ≥

Opt
2αB

Opt
· d(τ) + 2αB
· d(σ ) =

Opt
2αB

· d(τ 0 ).

)
0
• If d(σ ) > αB, then σ is partitioned into at most 2d(σ
αB paths of length αB each. The path σ of best profit
Opt
Opt
αB e
0
e 0
has φe(σ 0 ) ≥ 2·d(σ
) φ (σ ) ≥ 4 ; so φ (τ ) ≥ φ (σ ) ≥ 4 .

In either case r-tour τ 0 satisfies inequality (5.6), and since τ ← τ 0 at the end of the iteration, the invariant holds
for next iteration as well. This completes the proof of Theorem 18.

6

Adaptive Traveling Repairman

In this section we consider the adaptive traveling repairman problem (AdapTRP), where given a demand distribution, the goal is to find an adaptive strategy that minimizes the expected sum of arrival times at demand
vertices. As in adaptive TSP, we assume that the demand distribution D is specified explicitly in terms of its
support.
Definition 9 (Adaptive Traveling Repairman) The input is a metric (V, d), root r and demand distribution D
m
given by m distinct subsets {Si }m
i=1 with probabilities {pi }i=1 (which sum to one). The goal in AdapTRP is to
compute a decision tree T in metric (V, d) such that:
• the root of T is labeled with the root vertex r, and
• for each scenario i ∈ [m], the path TSi followed on input Si contains all vertices in Si .
The objective function is to minimize the expected latency ∑m
i=1 pi · Lat(TSi ), where Lat(TSi ) is the sum of arrival
times at vertices Si along path TSi .
We obtain an O(log2 n log m)-approximation algorithm for AdapTRP (Theorem 3). The high-level approach
here is similar to that for AdapTSP, but there are some important differences. Unlike AdapTSP, we can not
directly reduce AdapTRP to the isolation problem: so there is no analogue of Lemma 17 here. The following
example illustrates this.
Example 1 Consider an instance of AdapTRP on a star-metric with center r and leaves {v, u1 , · · · , un }. Edges
√
(r, ui ) have unit length for each i ∈ [n], and edge (r, v) has length n. There are m = n + 1 scenarios: scenario
S0 = {v} occurs with 1 − 1n probability; and for each i ∈ [n], scenario Si = {v, ui } occurs with n12 probability. The
optimal Isolation value for this instance is Ω(n) and any reasonable solution clearly will not visit vertex v: it
appears in all scenarios and hence provides no information. So if we first follow such an Isolation solution, the
arrival time for v is Ω(n); since S0 = {v} occurs with 1 − o(1) probability, the resulting expected latency is Ω(n).
√
However, the AdapTRP solution that first visits v, and then vertices {u1 , · · · , un } has expected latency O( n).
On the other hand, one can not ignore the “isolation aspect” in AdapTRP either.

20

Example 2 Consider another instance of AdapTRP on a star-metric with center r and leaves {vi }ni=1 ∪ {ui }ni=1 .
For each i ∈ [n], edge (r, vi ) has unit length and edge (r, ui ) has length n. There are n scenarios: for each i ∈ [n],
scenario Si = {vi , ui } occurs with 1n probability. The optimal values for both AdapTRP and Isolation are Θ(n).
Moreover, any reasonable AdapTRP solution will involve first isolating the realized scenario (by visiting vertices
vi s).
Hence, the algorithm needs to interleave the two goals of isolating scenarios and visiting high-probability
vertices. This will become clear in the construction of the latency group Steiner instances used by our algorithm
(Step 3 in Algorithm 6).
Algorithm Outline Although we can not reduce AdapTRP to Isolation, we are still able to use ideas from
the Isolation algorithm. The AdapTRP algorithm also follows an iterative approach and maintains a candidate
set M ⊆ [m] containing the realized scenario. We also associate conditional probabilities qi := ∑ pi p j for each
j∈M
scenario i ∈ M. In each iteration, the algorithm eliminates a constant fraction of scenarios from M: so the
number of iterations will be O(log m). Each iteration involves solving an instance of the latency group Steiner
(LGST) problem: recall Definition 8 and the O(log2 n)-approximation algorithm for LGST (Corollary 15). The
construction of this LGST instance is the main point of difference from the Isolation algorithm. Moreover, we
will show that the expected latency incurred in each iteration is O(log2 n) · Opt. Adding up the latency over all
iterations, would yield an O(log2 n log m)-approximation algorithm for AdapTRP.
Using LGST to partition scenarios M In each iteration, the algorithm formulates an LGST instance and
computes an r-tour τ using Corollary 15. The details are in Algorithm 6 below. An important property of
this tour τ is that the number of candidate scenarios after observing demands on τ will be at most |M|/2 (see
Claim 22).
Given a candidate set M of scenarios, it will be convenient to partition the vertices into two parts: H consists
of vertices which occur in more than half the scenarios, and L := V \ H consists of vertices occurring in at most
half the scenarios. In the LGST instance (Step 3 below), we introduce |Si ∩ H| + 1 groups (with suitable weights)
corresponding to each scenario i ∈ M.
Algorithm 6 PartnLat( hM, {qi }i∈M , {Si }i∈M i )
1: define Fv := {i ∈ M | v ∈ Si } for each v ∈ V .

n
o
Fv
|M|
2: let L := u ∈ V : |Fu | ≤ 2 , H := V \ L, and Dv :=
3:

M \ Fv

if v ∈ L
if v ∈ H

define instance G of LGST (Definition 8) on metric (V, d), root r and the following groups:
for each scenario i ∈ M,
- the main group Xi of scenario i has weight |Si ∩ L|pi and vertices (L ∩ Si ) ∪ (H \ Si ).
- for each v ∈ Si ∩ H, group Yiv has weight pi and vertices {v} ∪ (L ∩ Si ) ∪ (H \ Si ).

run the LGST algorithm (from Corollary 15) on instance G .
let τ := hr, v1 , v2 , · · · , vt−1 , ri be the r-tour 
returned.

if 1 ≤ k ≤ t − 1
Dvk \ ∪ j<k Dvj
t
5: let {Pk }k=1 be the partition of M where Pk :=

4:

6:

M \ ∪ j<t Dv j

if k = t

return tour τ = hr, v1 , v2 , · · · , vt−1 , ri and partition {Pk }tk=1 .

Claim 22 When |M| ≥ 2, partition {Pk }tk=1 returned by PartnLat satisfies |Pk | ≤ |M|/2, ∀k ∈ [t].

21

Proof: For each k ∈ [t − 1], we have Pk ⊆ Dvk and so |Pk | ≤ |M|/2. We now show that |Pt | ≤ 1 which would prove
the claim. Let V (τ) = {v1 , . . . , vt−1 } denote the vertices visited in the tour τ output by PartnLat. Consider any
S
i ∈ Pt : we will show that it is unique. By definition of Pt , we have i 6∈ t−1
k=1 Dvk . By the definition of group Xi
and sets Dv s, this means that Xi is not covered by V (τ). Since τ is a feasible solution to G , Xi ’s weight must be
zero, i.e. |Si ∩ L| = 0. Thus we have Si ⊆ H. Furthermore, if vk ∈ H \ Si for any k ∈ [t − 1] then i ∈ Dvk , which
implies i 6∈ Pt ; so H ∩V (τ) ⊆ Si . Note that each Yiv = {v} ∪ Xi (for v ∈ H ∩ Si = Si ) must be covered by τ, since
Yiv s have weight pi > 0. Also since Xi is not covered by V (τ), we must have v ∈ V (τ) for all v ∈ Si . Thus we
have Si ⊆ H ∩V (τ), and combined with the earlier observation, H ∩V (τ) = Si . This determines i ∈ M uniquely,
and so |Pt | = 1 ≤ |M|/2.

Final AdapTRP algorithm and analysis Given the above partitioning scheme, Algorithm 7 describes the
overall AdapTRP algorithm in a recursive manner.
Algorithm 7 AdapTRPhM, {qi }i∈M , {Si }i∈M i
1: If |M| = 1, visit the vertices in this scenario using the O(1)-approximation algorithm [FHR07] for deterministic traveling repairman, and quit.
2: run PartnLathM, {qi }i∈M i
let τ = (r, v1 , v2 , · · · , vt−1 , r) be the r-tour and {Pk }tk=1 be the partition of M returned.
3: let q0j := ∑i∈Pk qi for all j = 1 . . .t.
4: traverse tour τ and return directly to r after visiting the first vertex vk∗ (for k∗ ∈ [t]) that determines that the
realized scenario is in Pk∗ ⊆ M.
5: update the scenarios in Pk∗ by removing vertices visited in τ until vk∗ , i.e.
Si0 ← Si \ {v1 , . . . , vk∗ },
6:

for all i ∈ Pk∗ .

run AdapTRPhPk∗ , { qq0 i∗ }i∈Pk∗ , {Si0 }i∈Pk∗ i to recursively cover the realized scenario within Pk∗ .
k

The analysis for this algorithm is similar to that for the isolation problem (Section 3.1) and we follow the
same outline. For any sub-instance J of AdapTRP, let Opt(J ) denote its optimal value. Just as in the isolation
case (Claim 9), it can be easily seen that the latency objective function is also sub-additive.
Claim 23 For any sub-instance hM, {qi }i∈M , {Si }i∈M i and any partition {Pk }tk=1 of M,
q

∑tk=1 q0k · Opt(hPk , { q0i }i∈Pk , {Si }i∈Pk i)
k

≤

Opt(hM, {qi }i∈M , {Si }i∈M i),

(6.7)

where q0k = ∑i∈Pk qi for all 1 ≤ k ≤ t.
The next property we show is that the optimal cost of the LGST instance G considered in Steps (3)-(4) of
Algorithm 6 is not too high.
Lemma 24 For any instance J = hM, {qi }i∈M , {Si }i∈M i of AdapTRP, the optimal value of the latency group
Steiner instance G in Step 4 of Algorithm PartnLat(J ) is at most Opt(J ).
Proof: Let T be an optimal decision tree for the given AdapTRP instance J . Note that any internal node of
T , labeled v, has two children corresponding to the realized scenario being in Fv (yes child) or M \ Fv (no child).
Now consider the root-leaf path in T (and corresponding tour σ in the metric) which starts at r, and at any internal
node v, moves on to the no child if v ∈ L, and moves to the yes child if v ∈ H. We claim that this tour is a feasible
solution to G , the latency group Steiner instance G .

22

To see why, first consider any scenario i ∈ M that branched off from path σ in decision-tree T ; let v be the
vertex where the tree path of scenario i branched off from σ . If v ∈ L then by the way we defined σ , it follows
the “no” child of v, and so v ∈ Si ∩ L. On the other hand, if v ∈ H, then it must be that v ∈ H \ Si (again from the
way σ was defined). In either case, v ∈ (Si ∩ L) ∪ (H \ Si ), and hence visiting v covers all groups, associated with
scenario i, i.e. Xi and {Yiv | v ∈ Si ∩ H}. Thus σ covers all groups of all the scenarios that branched off it in T .
Note that there is exactly one scenario (say a ∈ M) that does not branch off σ ; scenario a traverses σ in T .
Since T is a feasible solution for AdapTRP, σ must visit every vertex in Sa . Therefore σ covers all the groups
associated with scenario a: clearly {Yav | v ∈ Sa ∩ H} are covered; Xa is also covered unless Sa ∩ L = 0/ (however
in that case group Xa has zero weight and does not need to be covered- see Definition 8). Thus σ is a feasible
solution to G .
We now bound the latency cost of tour σ for instance G . In path σ , let αi (for each i ∈ M) denote the coverage
time for group Xi , and βiv (for i ∈ M and v ∈ Si ∩ H) the coverage time for group Yiv . The next claim shows that
the latency of σ for instance G is at most Opt(J ).
Claim 25 The expected cost of T , Opt(J ) ≥ ∑i∈M pi · |L ∩ Si | · αi + ∑i∈M ∑v∈Si ∩H pi · βiv , which is exactly the
latency of tour σ for the latency group Steiner instance G .
Proof: Fix any i ∈ M; let σi denote the shortest prefix of σ containing a vertex from Xi . Note that by definition,
σi has length αi . We will lower bound separately the contributions of Si ∩ L and Si ∩ H to the cost of T .
As all but the last vertex in σi are from (L \ Si ) ∪ (H ∩ Si ), by definition of σ , the path TSi traced in the
decision-tree T when scenario i is realized, agrees with this prefix σi . Moreover, no vertex of Si ∩ L is visited
before the end of σi . So under scenario Si , the total arrival time for vertices L ∩ Si is at least |L ∩ Si | · αi . Hence
Si ∩ L contributes at least pi · |L ∩ Si | · αi towards Opt(J ).
Now consider some vertex v ∈ Si ∩ H; let σiv denote the shortest prefix of σ containing a Yiv -vertex. Note that
v
σi has length βiv , and it is a prefix of σi since Yiv ⊇ Xi . As observed earlier, the path traced in decision tree T under
scenario i contains σi : so vertex v is visited (under scenario i) only after tracing path σiv . So the contribution of v

(under scenario i) to Opt(J ) is at least pi · βiv , i.e. the contribution of Si ∩ H is at least ∑v∈Si ∩H pi · βiv
Thus we have demonstrated a feasible solution to G of latency at most Opt(J ).

It remains to bound the expected additional latency incurred in Step 4 of Algorithm 7 when a random scenario
is realized. Below we assume a ρ = O(log2 n) approximation algorithm for latency group Steiner tree (from
Corollary 15).
Lemma 26 At the end of Step 4 of AdapTRPhM, {qi }i∈M , {Si }i∈M i, the realized scenario lies in Pk∗ . The expected
increase in latency due to this step is at most 2 ρ · Opt(hM, {qi }i∈M , {Si }i∈M i).
Proof: The proof that the realized scenario always lies in the Pk∗ determined in Step 4 is identical to that in
Claim 8 of the Isolation algorithm, and is omitted. We now bound the expected latency incurred. In the solution
τ to the latency group Steiner instance G , define αi as the coverage time for group Xi , ∀i ∈ M; and βiv as the
coverage time for group Yiv , ∀i ∈ M and v ∈ Si ∩ H.
Let i denote the realized scenario. Suppose that k∗ = ` ≤ t − 1 in Step 4. Then by definition of the parts
T
Pk s, we have v` ∈ Xi = (Si ∩ L) ∪ (H \ Si ) and Xi {v1 , . . . , v`−1 } = 0.
/ So the length along τ until v` equals αi .
Moreover the total length spent in this step is at most 2 · αi , to travel till v` and then return to r (this uses the
symmetry and triangle-inequality properties of the metric). So the latency of any Si -vertex increases by at most
this amount. Furthermore we claim that the latency of any v ∈ Si ∩ H increases by at most 2 · βiv : this is clearly
true if βiv = αi ; on the other hand if βiv < αi then v is visited before v` and so it only incurs latency βiv . So the
increase in latency of Si is at most 2 ∑v∈Si ∩H βiv + 2 · |Si ∩ L| αi .

23

If k∗ = t then by the proof of Claim 22 the realized scenario i satisfies: Si ⊆ H, group Xi is not visited by τ
(so αi is undefined), and all of Si is visited by τ. In this case the total latency of Si is ∑v∈Si ∩H βiv which is clearly
at most 2 ∑v∈Si ∩H βiv + 2 · |Si ∩ L| αi ; note that |Si ∩ L| = 0 here.


Thus the expected latency incurred in Step 4 is at most 2 ∑i∈M pi · |Si ∩ L| αi + ∑v∈Si ∩H βiv which is twice
the latency of τ for the latency group Steiner instance G . Finally, since τ is a ρ-approximate solution to G and
using Lemma 24, we obtain the claim.

Finally, combining Claim 22, Lemma 26 and Claim 23, by a proof identical to that of Theorem 4, it follows
that the final AdapTRP solution has cost O(log2 n log m) · Opt. This completes the proof of Theorem 3.
We note that for the AdapTRP problem on metrics induced by a tree, our algorithm achieves an O(log n log m)
approximation ratio (the guarantees in Theorem 18 and Corollary 15 improve by a logarithmic factor on tree
metrics). There is also an Ω(log1−ε n)-hardness of approximation the AdapTRP problem on tree metrics [Nag09].
So there is still a logarithmic gap between the best upper and lower bounds for the AdapTRP problem on tree
metrics. In going from tree metrics to general, we lose another logarithmic factor in the approximation ratio.

7

Concluding Remarks

In this paper, we studied the problem of constructing optimal decision trees; this widely studied problem was
previously known to admit logarithmic approximation algorithms for the case of uniform costs or uniform
probabilities. The greedy algorithms used in these cases do not extend to the case of non-uniform costs and
probabilities, and we gave a new algorithm that seeks to be greedy with respect to two different criteria; our
O(log m)-approximation is asymptotically optimal. We then considered a generalization to the adaptive traveling
salesman problem, and obtained an O(log2 n log m)-approximation algorithm for this adaptive TSP problem. We
also showed that any asymptotic improvement on this result would imply an improved approximation algorithm
for the group Steiner tree problem, which is a long-standing open problem. Finally, we gave an O(log2 n log m)approximation algorithm for the adaptive traveling repairman problem— closing the gap between the known
upper and lower bounds in this case remains an interesting open problem.

Acknowledgments.
A preliminary version appeared in the proceedings of the International Colloquium on Automata, Languages and
Programming (ICALP), 2010. We thank Ravishankar Krishnaswamy for many useful conversations; the results
on the adaptive traveling repairman problem were obtained in joint discussions, and we thank him for permission
to include the results here. We also thank the MOR referees for helpful suggestions that improved the presentation
of the paper. A. Gupta’s research was supported in part by NSF awards CCF-0448095 and CCF-0729022, and an
Alfred P. Sloan Fellowship. R. Ravi’s research was supported in part by NSF grant CCF-0728841.

References
[AH12]

Micah Adler and Brent Heeringa. Approximating optimal binary decision trees. Algorithmica, 62(34):1112–1121, 2012.

[BCC+ 94] A. Blum, P. Chalasani, D. Coppersmith, W. R. Pulleyblank, P. Raghavan, and M. Sudan. The minimum latency problem. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing,
pages 163–171, 1994.

24

[BGL+ 12] Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, and Atri Rudra. When
LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica,
63(4):733–762, 2012.
[CCGG98] Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha. Rounding via trees: deterministic approximation algorithms for group Steiner trees and k median. In Proceedings of the 30th
Annual ACM Symposium on Theory of Computing, pages 114–123, 1998.
[CGRT03] K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar. Paths, trees, and minimum latency tours. In
Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pages 36–
45, 2003.
[Chr77]

N. Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. GSIA,
CMU-Report 388, 1977.

[CP05]

Chandra Chekuri and Martin Pál. A recursive greedy algorithm for walks in directed graphs. In
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 245–
253, 2005.

[CPR+ 11] Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Pranjal Awasthi, and Mukesh K.
Mohania. Decision trees for entity identification: Approximation algorithms and hardness results.
ACM Transactions on Algorithms, 7(2):15, 2011.
[CPRS09] Venkatesan Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, and Yogish Sabharwal. Approximating Decision Trees with Multiway Branches. In ICALP, pages 210–221, 2009.
[Das04]

Sanjoy Dasgupta. Analysis of a greedy active learning strategy. In Advances in Neural Information
Processing Systems (NIPS), 2004.

[DGV08]

Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Approximating the stochastic knapsack
problem: The benefit of adaptivity. Math. Oper. Res., 33(4):945–964, 2008.

[FHR07]

Jittat Fakcharoenphol, Chris Harrelson, and Satish Rao. The k-traveling repairmen problem. ACM
Transactions on Algorithms, 3(4), 2007.

[FLT04]

Uriel Feige, László Lovász, and Prasad Tetali. Approximating min sum set cover. Algorithmica,
40(4):219–234, 2004.

[FRT04]

Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary
metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004.

[Gar96]

Naveen Garg. A 3-Approximation for the Minimum Tree Spanning k Vertices. In Proceedings of the
37th Annual IEEE Symposium on Foundations of Computer Science, pages 302–309, 1996.

[GB09]

Andrew Guillory and Jeff Bilmes. Average-Case Active Learning with Costs. In Algorithmic Learning Theory, pages 141–155. Springer Berlin / Heidelberg, 2009.

[GG74]

M.R. Garey and R.L. Graham. Performance bounds on the splitting algorithm for binary testing.
Acta Informatica, 3:347–355, 1974.

[GHR06]

Anupam Gupta, Mohammad T. Hajiaghayi, and Harald Räcke. Oblivious network design. In SODA
’06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages
970–979, 2006.

25

[GK11]

Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active
learning and stochastic optimization. J. Artif. Intell. Res. (JAIR), 42:427–486, 2011.

[GKR00]

N. Garg, G. Konjevod, and R. Ravi. A Polylogarithmic Approximation Algorithm for the Group
Steiner Tree Problem. Journal of Algorithms, 37(1):66–84, 2000.

[GM09]

Sudipto Guha and Kamesh Munagala. Multi-armed bandits with metric switching costs. In ICALP,
pages 496–507, 2009.

[GV06]

Michel Goemans and Jan Vondrák. Stochastic covering and adaptivity. In LATIN 2006: Theoretical
informatics, volume 3887 of Lecture Notes in Comput. Sci., pages 532–543. Springer, Berlin, 2006.

[HK03]

Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Proceedings of the
35th Annual Symposium on Theory of Computing, pages 585–594, 2003.

[HLS10]

Ting He, Kang-Won Lee, and Ananthram Swami. Flying in the dark: controlling autonomous data
ferries with partial observations. In MobiHoc, pages 141–150, 2010.

[HR77]

Laurent Hyafil and Ronald L. Rivest. Constructing optimal binary decision trees is NP-complete.
Information Processing Lett., 5(1):15–17, 1976/77.

[Jai88]

Patrick Jaillet. A priori solution of a travelling salesman problem in which a random subset of the
customers are visited. Operations Research, 36 (6), 1988.

[JLN+ 05] Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. Universal
approximations for TSP, Steiner tree, and set cover. In STOC ’05: Proceedings of the thirty-seventh
annual ACM symposium on Theory of computing, pages 386–395, 2005.
[KPB99]

S. Rao Kosaraju, Teresa M. Przytycka, and Ryan S. Borgstrom. On an Optimal Split Tree Problem. In
Proceedings of the 6th International Workshop on Algorithms and Data Structures, pages 157–168,
1999.

[Lov85]

Donald W. Loveland. Performance bounds for binary testing with arbitrary weights. Acta Inform.,
22(1):101–114, 1985.

[LPRY08] Zhen Liu, Srinivasan Parthasarathy, Anand Ranganathan, and Hao Yang. Near-optimal algorithms
for shared filter evaluation in data stream systems. In SIGMOD ’08: Proceedings of the 2008 ACM
SIGMOD international conference on Management of data, pages 133–146, 2008.
[MSW07] Kamesh Munagala, Utkarsh Srivastava, and Jennifer Widom. Optimization of continuous queries
with shared expensive filters. In PODS ’07: Proceedings of the twenty-sixth ACM SIGMODSIGACT-SIGART symposium on Principles of database systems, pages 215–224, 2007.
[Nag09]

Viswanath Nagarajan. Approximation Algorithms for Sequencing Problems. PhD thesis, Tepper
School of Business, Carnegie Mellon University, 2009.

[Now11]

Robert D. Nowak. The geometry of generalized binary search. IEEE Transactions on Information
Theory, 57(12):7893–7906, 2011.

[SRJB03] Rahul C. Shah, Sumit Roy, Sushant Jain, and Waylon Brunette. Data mules: modeling and analysis
of a three-tier architecture for sparse sensor networks. Ad Hoc Networks, 1(2-3):215–233, 2003.

26

[SS08]

F. Schalekamp and D. Shmoys. Algorithms for the universal and a priori TSP. Operations Research
Letters, 36(1):1–3, 2008.

[ST08]

David Shmoys and Kunal Talwar. A Constant Approximation Algorithm for the a priori Traveling
Salesman Problem. In Proceedings of the 13th International Conference on Integer Programming
and Combinatorial Optimization, pages 331–343, 2008.

[Svi04]

M. Sviridenko. A note on maximizing a submodular set function subject to knapsack constraint.
Operations Research Letters, 32:41–33, 2004.

[ZA03]

Wenrui Zhao and Mostafa H. Ammar. Message ferrying: Proactive routing in highly-partitioned
wireless ad hoc networks. In FTDCS, pages 308–314, 2003.

[ZAZ04]

Wenrui Zhao, Mostafa H. Ammar, and Ellen W. Zegura. A message ferrying approach for data
delivery in sparse mobile ad hoc networks. In MobiHoc, pages 187–198, 2004.

[ZAZ05]

Wenrui Zhao, Mostafa H. Ammar, and Ellen W. Zegura. Controlling the mobility of multiple data
transport ferries in a delay-tolerant network. In INFOCOM, pages 1407–1418, 2005.

A

Hardness of Approximation for AdapTSP

We show that AdapTSP is at least as hard to approximate as group Steiner tree.
Theorem 27 If there is an α-approximation algorithm for AdapTSP then there is an (α + o(1))-approximation
algorithm for group Steiner tree. Hence AdapTSP is Ω(log2−ε n) hard to approximate even on tree metrics.
Proof: This reduction is similar to the reduction [CPR+ 11] from set-cover to the optimal decision tree problem;
we give a proof in context of AdapTSP for completeness.
Consider an arbitrary instance of group Steiner tree on metric (V, d) with root r and groups X1 , · · · , Xg ⊆ V ;
let Opt denote its optimal value. Assume without loss of generality that Xi 6= X j for all i 6= j, and the minimum
non-zero distance in d is one. We construct an instance of AdapTSP as follows. Let V 0 = V ∪ {s} where s is a
new vertex (representing a copy of r), and define metric d 0 on V 0 as:

 0
V
d(u, v) for u, v ∈ V
0
d (u, v) :=
,
∀(u, v) ∈
d(u, r) for u ∈ V, v = s
2
There are g + 1 scenarios in the AdapTSP instance: Si := Xi ∪ {s} for i ∈ [g], and Sg+1 := {s}, with probabilities
 1
if 1 ≤ i ≤ g
gL
pi :=
,
1
1 − L if i = g + 1

Above L  2n · maxu,v d(u, v) is some large value. The root in the AdapTSP instance remains r. Let Opt0 denote
the optimal value time of this instance. We will show that (1 − o(1)) · Opt ≤ Opt0 ≤ Opt + 1 which would prove
the theorem.

(A) 1 − L1 Opt ≤ Opt0 . Consider the optimal solution to the AdapTSP instance; let σ denote the r-tour traversed by this decision tree under scenario Sg+1 . We now argue that σ is a feasible solution to the group Steiner
tree instance, i.e., Opt ≤ d(σ ). Suppose for a contradiction that σ does not visit any Xi -vertex for some i ∈ [g].
Then observe that the r-tour traversed by this decision tree under scenario Si is also σ , since the decision tree
can not distinguish scenarios Si and Sg+1 (the only way to do this is by visiting some Xi -vertex). However this

27

violates the requirement that the tour (namely σ ) under scenario Si must visit all vertices Si ⊇ Xi . Finally, we
have Opt0 ≥ (1 − L1 ) · d(σ ) ≥ 1 − L1 Opt as required.
(B) Opt0 ≤ Opt + 1. Let τ denote an optimal r-tour for the given GST instance, so d(τ) = Opt. Consider the
following solution for AdapTSP:
1. Traverse r-tour τ to determine whether or not Xg+1 is the realized scenario.
2. If no demands observed on τ (i.e. scenario Sg+1 is realized), visit vertex s and stop.
3. If some demand observed on τ (i.e. one of scenarios {Si }gi=1 is realized), then visit all vertices in V along
an arbitrary r-tour and stop.
It is clear that this decision tree is feasible for the AdapTSP instance. For any i ∈ [g + 1], let πi denote the
r-tour traversed under scenario Si in the above AdapTSP decision tree. We have d(πg+1 ) = d(τ) ≤ Opt, and
d(πi ) ≤ 2n · maxu,v d(u, v) ≤ L for all i ∈ [g]. Thus the resulting AdapTSP objective is at most:


1
1
1−
· Opt + g ·
· L ≤ Opt + 1
L
gL


Thus we have the desired reduction.

28

