Compact, Provably-Good LPs for Orienteering and
Regret-Bounded Vehicle Routing∗
Zachary Friggstad†

Chaitanya Swamy‡

arXiv:1708.01335v1 [] 4 Aug 2017

Abstract
We develop polynomial-size LP-relaxations for orienteering and the regret-bounded vehicle routing
problem (RVRP) and devise suitable LP-rounding algorithms that lead to various new insights and approximation results for these problems. In orienteering, the goal is to find a maximum-reward r-rooted
path, possibly ending at a specified node, of length at most some given budget B. In RVRP, the goal is
to find the minimum number of r-rooted paths of regret at most a given bound R that cover all nodes,
where the regret of an r-v path is its length − crv .
For rooted orienteering, we introduce a natural bidirected LP-relaxation and obtain a simple 3approximation algorithm via LP-rounding. This is the first LP-based guarantee for this problem. We
also show that point-to-point (P2P) orienteering can be reduced to a regret-version of rooted orienteering at the expense of a factor-2 loss in approximation. For RVRP, we propose two compact LPs that lead
to significant improvements, in both approximation ratio and running time, over the approach in [14].
One of these is a natural modification of the LP for rooted orienteering; the other is an unconventional
formulation that is motivated by certain structural properties of an RVRP-solution, which leads to a
15-approximation algorithm for RVRP.

1

Introduction

Vehicle-routing problems (VRPs) constitute a broad class of optimization problems that find a wide range
of applications and have been widely studied in the Operations Research and Computer Science literature
(see, e.g., [19, 23, 9, 6, 4, 11]). Despite this extensive study, we have rather limited understanding of LPrelaxations for VRPs (with TSP and the minimum-latency problem, to a lesser extent, being exceptions),
and this has been an impediment in the design of approximation algorithms for these problems.
Motivated by this gap in our understanding, we investigate whether one can develop polynomial-size
(i.e., compact) LP-relaxations with good integrality gaps for VRPs, focusing on the fundamental orienteering problem [18, 6, 11] and the related regret-bounded vehicle routing problem (RVRP) [7, 14]. In orienteering, we are given rewards associated with clients located in a metric space, a length bound B, a start, and
possibly end, location for the vehicle, and we seek a route of length at most B that gathers maximum reward.
This problem frequently arises as a subroutine when solving VRPs, both in approximation algorithms—e.g.,
for minimum-latency problems (MLPs) [5, 12, 8, 21], TSP with time windows [4], RVRP [7, 14]—as well as
in computational methods where orienteering corresponds to the “pricing” problem encountered in solving
set covering/partitioning LPs (a.k.a configuration LPs) for VRPs via a column-generation or branch-cutand-price method. In RVRP, we have a metric space {cuv } on client locations, a start location r, and a
regret bound R. The regret of a path P starting at r and ending at location v is c(P ) − crv . The goal in
RVRP is to find a minimum number of r-rooted paths of regret at most R that visit all clients.
∗

A preliminary version [15] appeared in the Proceedings of the 19th Conference on Integer Programming and Combinatorial
Optimization, 2017.
†
zacharyf@ualberta.ca. Dept. of Computer Science, Univ. Alberta, Edmonton, AB T6G 2E8. Supported by the Canada
Research Chairs program and an NSERC Discovery grant.
‡
cswamy@uwaterloo.ca. Dept. of Combinatorics and Optimization, Univ. Waterloo, Waterloo, ON N2L 3G1. Supported
in part by NSERC grant 327620-09 and an NSERC Discovery Accelerator Supplement Award.

1

Our contributions. We develop polynomial-size LP-relaxations for orienteering and RVRP and devise
suitable rounding algorithms for these LPs, which lead to various new insights and approximation results
for these problems.
In Section 3, we introduce a natural, compact LP-relaxation for rooted orienteering, wherein only the
vehicle start node is specified, and design a simple rounding algorithm to convert an LP-solution to an
integer solution losing a factor of at most 3 in the objective value. This is the first LP-based approximation
guarantee for orienteering. In contrast, all other approaches for orienteering utilize dynamic programming
(DP) to stitch together suitable subpaths.
In Section 4, we consider the more-general point-to-point (P2P) orienteering problem, where both the
start and end nodes of the vehicle are specified. We present a novel reduction showing that P2P-orienteering
can be reduced to a regret-version of rooted orienteering, wherein the length bound is replaced by a regret
bound, incurring a factor-2 loss (Theorem 4.1). No such reduction to a rooted problem was known previously, and all known algorithms for P2P-orienteering rely on approximations to suitable P2P-path problems.
Typically, constraining a VRP by requiring that routes include a fixed node t causes an increase in the route
lengths of the unconstrained problem (as we need to attach t to the routes); this would violate the length
bound in orienteering, but, notably, we devise a way to avoid this in our reduction. We believe that the
insights gained from our reduction may find further application. Our results for rooted orienteering translate to the regret-version of orienteering, and combined with the above reduction, give a compact LP for
P2P-orienteering having integrality gap at most 6.
Although we do not improve the current-best approximation factor of (2 + ) for orienteering [11], we
believe that our LP-based approach is nevertheless appealing for various reasons. First, our LP-rounding
algorithms are quite simple, and arguably, simpler than the DP-based approaches in [6, 11]. Second, our LPbased approach offers the promising possibility that, by leveraging the key underlying ideas, one can obtain
strong, compact LP-relaxations for other problems that utilize orienteering. Indeed, we already present
evidence of such benefits by showing in Section 5.1 that our LP-insights for rooted orienteering yield a
compact, provably-good LP for RVRP. (We remark that various configuration LPs considered for VRPs
give rise to P2P-orienteering as the dual-separation problem, and utilizing our compact orienteering-LP
in the dual could yield another way of obtaining a compact LP.) Finally, LP-based insights often tend to
be powerful and have the potential to result in both improved guarantees, and algorithms for variants of
the problem. In fact, we suspect that our orienteering LPs, (R-O), (P2P-O), are better than what we have
accounted for, and believe that they are a promising means of improving the state-of-the-art for orienteering.
Section 5 considers RVRP, and proposes two compact LP-relaxations for RVRP and corresponding
rounding algorithms. Our LP-based algorithms not only yield improvements over the current-best 28.86approximation for RVRP [14], but also result in substantial savings in running time compared to the algorithm in [14], which involves solving a configuration LP (with an exponential number of path variables)
using the Ω(n1/ )-time (2 + )-approximation algorithm for orienteering in [11] as a subroutine. The first
LP for RVRP is a natural modification of our LP for rooted orienteering, which we show has integrality
gap at most 27 (Theorem 5.1). In Section 5.2, we formulate a rather atypical LP-relaxation (R2) for RVRP
by exploiting certain key structural insights for RVRP. We observe that an RVRP-solution can be regarded
as a collection of distance-increasing rooted paths covering some sentinel nodes S and a low-cost way of
connecting the remaining nodes to S, and our LP aims to find the best such solution. We design a rounding
algorithm for this LP that leads to a 15-approximation algorithm for RVRP, which is a significant improvement over the guarantee obtained in [14].
Finally, in Section 6, we observe that our techniques imply that the integrality gap of a Held-Karp style
LP for the asymmetric-TSP (ATSP) path problem is 2 for the class of asymmetric metrics induced by the
regret objective.
To give an overview of our techniques, a key tool that we use in our rounding algorithms, which also
motivates our LP-relaxations, is an arborescence-packing result of [3] showing that an r-preflow x ∈ RA
+ in
2



a digraph D = (N, A) (i.e., x δ in (v) ≥ x δ out (v) ∀v 6= r) dominates a weighted collection of r-rooted
(non-spanning) out-arborescences (Theorem 2.3). An r-preflow x in the bidirected version of our metric,
D, is a natural relaxation of an r-rooted path, and the r
u connectivity under x abstracts whether u lies
on this path. This leads to our LP (R-O) for (rooted) orienteering. The idea behind the rounding is that if we
know the node v on the optimum path with maximum crv value, then we can enforce that our the LP-preflow
x is consistent with v. Hence, we can decompose x into arborescences containing v of average length at
most B, which yield r-v paths of average regret at most 2(B − crv ). These in turn can be converted (see
Lemma 2.1) into a weighted collection of paths of total weight at most 3, where each path has regret at most
B − crv and ends at some node u with cru ≤ crv ; returning the maximum-reward path in this collection
yields a 3-approximation.
Related work. The orienteering problem seems to have been first defined in [18]. Blum et al. [6] gave the
first O(1)-factor approximation for rooted orienteering. They obtained an approximation ratio of 4, which
was generalized to P2P-orienteering, and improved to 3 [4] and then to 2 +  [11].
Orienteering is closely related to the k-{stroll, MST, TSP} problems, which seek a minimum-cost
rooted {path,tree,tour} respectively spanning at least k nodes (so the roles of objective and constraint are
interchanged). k-MST has a rich history of study that culminated in a factor-2 approximation for both
k-MST and k-TSP [16]. Chaudhuri et al. [10] obtained a (2 + )-approximation algorithm for k-stroll.
They also showed that for certain values of k, one can obtain a tree spanning k nodes and containing two
specified nodes r, t, of cost at most the cheapest r-t path spanning k nodes. In particular, this holds for
k = n, and yields an alternative way of obtaining a 2-approximation algorithm for the minimum-regret
TSP-path problem considered in Section 6. The orienteering algorithms in [6, 4, 11] are all based on first
obtaining suitable subpaths by approximating the min-excess path problem using a k-stroll algorithm as a
subroutine, and then stitching together these subpaths via a DP. (For a rooted path, the notions of excess and
regret coincide; we use the term regret as it is more in line with the terminology used in the vehicle-routing
literature [22, 20].)
The use of regret as a vehicle-routing objective seems to have been first considered in [22], who present
various heuristics, and RVRP is sometimes referred to as the schoolbus problem in the literature [22, 20, 7].
Bock et al. [7] were the first to consider RVRP from an approximation-algorithms perspective. They obtain approximation factors of O(log n) for general metrics and 3 for tree metrics. Subsequently, Friggstad and Swamy [14] gave the first constant-factor approximation algorithm for RVRP, obtaining a 28.86approximation via an LP-rounding procedure for a configuration LP.

2

Preliminaries and notation

Both orienteering and RVRP involve a complete undirected graph G = ({r} ∪ V, E), where r is a distinguished root (or depot) node, and metric edge costs {cuv }. Let n = |V | + 1. We call a path P in G rooted if
it begins at r. We always think of the nodes on P as being ordered in increasing order of their distance along
P from r, and directing P away from r means that we direct each edge uv ∈ P from u to v if u precedes
v (under this ordering). We use Dv to denote crv for all v ∈ V ∪ {r}. Let T denote P
the collection of all
E
r-rooted trees in G. For a vector d ∈ R , and a subset FP⊆ E, we use d(F ) to denote e∈F de . Similarly,
for a vector d ∈ RV and S ⊆ V , we use d(S) to denote v∈S dv .
Regret metric and RVRP. For every ordered pair u, v ∈ V ∪ {r}, define the regret distance (with respect
reg
to r) to be creg
uv := Du + cuv − Dv . The regret distances {cuv } form an asymmetric metric that we call the
reg
regret metric. The regret of a node v lying on a rooted path P is given by creg
P (v) := cP (v) − Dv = (c length of the r-v portion of P ), where cP (v) is the length of the r-v subpath of P . Define the regret of P to
3

be creg (P ), which is also the regret of the end-node of P . Observe that creg (Z) = c(Z) for any cycle Z. We
utilize the following results from [14].
Lemma 2.1 ([14]) Let R ≥ 0. Given rooted paths P1 , . . . , Pk with total
S regret αR, we can efficiently find
at most k + α rooted paths, each having regret at most R, that cover ki=1 Pi .
P
Theorem 2.2 ([14]) Let x = (xP )P ∈P be a weighted collection ofProoted paths such
P that reg P ∈P:v∈P xP ≥
1 for all v ∈ V . Let R ≥ 0 be some given parameter. Let k = P ∈P xP and P ∈P c (P )xP = αR.

 
6
Then, for any θ ∈ (0, 1), we can round x to obtain a collection of at most 1−θ
+ 1θ α + kθ rooted paths
each of regret at most R that cover all nodes in V .
Preflows and arborescence
packing. Let
D = ({r} ∪ V, A) be a digraph. We say that a vector x ∈ RA
+


is an r-preflow if x δ in (v) ≥ x δ out (v) for all v ∈ V . When r is clear from the context, we simply say
preflow. A key tool that we exploit is an arborescence-packing result of Bang-Jensen et al. [3] showing that
we can decompose a preflow into out-arborescences rooted at r, and this can be done in polytime [21]. By
an out-arborescence rooted at r, we mean a subgraph B whose undirected version is a tree containing r,
and where every node spanned by B except r has exactly one incoming arc in B.
Theorem 2.3 ([3, 21]) Let D = ({r} ∪ V, A) be a digraph and x ∈ RA
+ be a preflow. Let λv :=
min{v}⊆S⊆V x δ in (S) be the r
v “connectivity” in D under capacities {xa }a∈A . Let K > 0 be
rational. P
We can obtain out-arborescences
B1 , . . . , Bq rooted P
at r, and rational weights
γ1 , . . . , γ q ≥ 0

P
q
such that i=1 γi = K, i:a∈Bi γi ≤ xa for all a ∈ A, and i:v∈Bi γi = min K, λv } for all v ∈ V .
Moreover, such a decomposition can be computed in time poly(|V |, size of K).

3

Rooted orienteering

In the rooted orienteering problem, we have a complete undirected graph G = ({r} ∪ V, E), metric edge
costs {cuv }, a distance bound B ≥ 0, and nonnegative node rewards {ρ(v)}v∈V . The goal is to find a rooted
path with cost at most B that collects the maximum reward. Whereas all current approaches for orienteering
rely on a dynamic program to stitch together suitable subpaths, we present a simple LP-rounding-based
3-approximation algorithm for rooted orienteering.
Let D = ({r} ∪ V, A) denote the bidirected version of G, where both (u, v) and (v, u) get cost cuv . To
introduce our LP and our rounding algorithm, first suppose that we know a node v on the optimum path that
has maximum distance Dv among all nodes on the optimum path. In our relaxation, we model the path as
one unit of flow x ∈ RA
+ that exits r, visits only nodes u with Du ≤ Dv and v to an extent of 1, and has cost
v
at most B. Since we do not know the endpoint of our path, we relax x to be a preflow.
P Letting zuvdenote the
r
u connectivity (under capacities {xa }), the reward earned by x is rewd(x) := u∈V ρ(u)zu .
Our rounding procedure is based on the insight that Theorem 2.3 allows us to view x as a convex
combination of arborescences, which we regard as r-rooted trees in G. Converting each tree into an r-v path
(by standard doubling and shortcutting), we get a convex combination of rooted paths of average reward
rewd(x), and average cost at most 2B − Dv , and hence average creg -cost at most 2(B − Dv ). Applying
Lemma 2.1 to this collection, we then obtain a weighted collection of rooted paths of total weight at most 3
earning the same total reward, where each path has regret at most B − Dv , and hence, cost at most B (since
it ends at some node u with Du ≤ Dv ). Thus, the maximum-reward path in this collection yields a feasible
solution with reward at least rewd(x)/3.
Finally, we circumvent the need for “guessing” v by using variables zvv to indicate if v is the maximumdistance node on the optimum path. We impose that we have a preflow xv of value zvv that visits v to an

4

extent of zvv , and only visits nodes u with Du ≤ Dv , and zuv is now the r
xv . (Note that r ∈
/ V .)
X
max
ρ(u)zuv

u connectivity under capacities
(R-O)

u,v∈V

s.t.



xv (δ in (u) ≥ xv δ out (u)

xv δ in (u) = 0

xv δ in (S) ≥ zuv
X
ca xva ≤ Bzvv

∀u, v ∈ V

(1)

∀u, v ∈ V : Du > Dv

(2)

∀v ∈ V, S ⊆ V, u ∈ S

(3)

∀v ∈ V

(4)

a∈A


xv δ out (r) = zvv

X

∀v ∈ V,

zvv = 1,

x, z ≥ 0.

v

This formulation can be converted to a compact LP by introducing flow variables f u,v = {fau,v }a∈A , and
v
u,v
v
encoding the cut constraints (3) by imposing that f u,v
r to
 u.
 ≤ x , and that f v sendsv zu inunits of flowv from
v
in
v
Observe that: (a) if Du > Dv then zu ≤ x δ (u) = 0; (b) we have zu ≤ x δ (V ) = x δ out (r) =
zvv for all u, v. Let (x∗ , z ∗ ) be an optimal solution to (R-O), of value OPT .
Theorem 3.1 We can round (x∗ , z ∗ ) to a rooted-orienteering solution of value at least OPT /3.
Proof : For each v with zv∗v > 0 we apply Theorem 2.3 with K = zv∗v to obtain r-rooted out-arborescences,
which we view as rooted trees in G, and associated
{γTv }TP
∈T ; recall that T is the
P v nonnegative
P weights
∗v
v
∗v
∗v
collection
of
all
r-rooted
trees.
So
we
have
γ
=
z
,
γ
c(T
)
≤
v
T T
T T
a ca xa ≤ Bzv , and
P
v
∗v
T
T :u∈T γT ≥ zu for all u ∈ V . Note that for every T with γv > 0, we have v ∈ T , and Du ≤ Dv
for all u ∈ T (as otherwise, we have x∗v δ in (u) = 0). For every v and every tree T with γTv > 0, we do
the following. First, we double the edges not lying on the r-v path of T and shortcut to obtain a simple r-v
path PTv . So
X
X

(5)
γTv creg (PTv ) ≤ 2
γTv c(T ) − Dv = 2zv∗v (B − Dv ).
T

T
creg (P v )

Next, we use Lemma 2.1 with regret-bound B − Dv to break PTv into a collection PTv of at most 1 + B−DTv
rooted paths, each having creg -cost at most B − Dv . Note that if B = Dv , then creg (PTv ) = 0, and we use
the convention that 0/0 = 0, so |PTv | = 1 in this case. Each path in PTv ends at a vertex u with Du ≤ Dv ,
so its c-cost is at most B. Now, for all v ∈ V , we have
X
X
X
X
γTv
ρ(P ) =
γTv ρ(PTv ) ≥
ρ(u)zu∗v
(6)
P ∈PTv

T

X

γTv |PTv | ≤

T

u

T

X



γTv 1 +

creg (PTv )
B−Dv



≤ zv∗v + 2zv∗v = 3zv∗v

where the last inequality in (7) follows from (5). Therefore, the maximum-reward path in
earns reward at least X
.X
 P ρ z ∗v
X
P u∗vu = OPT /3.
γTv
ρ(P )
γTv |PTv | ≥ 3v,u
z
v,T

(7)

T

P ∈PTv

v

v
v,T :γTv >0 PT

S

v

v,T

Remark 3.2 The above
algorithm and analysis
that the weaker
we replace the con
 LP where
P v also showP
v
out
v
v
out
v
straints x δ (r) = zv for all v ∈ V , v zv = 1 with v x δ (r) = 1, zu ≤ zvv for all u, v ∈ V ,
also has integrality gap at most 3.
5

Regret orienteering. The following variant of rooted orienteering, which we call regret orienteering, will
be useful in Section 4. In regret orienteering, instead of a cost bound B, we are given a regret bound R,
and we seek a rooted path of regret at most R that collects the maximum reward. The LP-relaxation for
v
regret-orienteering is very similar to (R-O); the only changes are
indicates if v is the end node
Pthat zv now
of the optimum path, and so we drop (2) and replace (4) with a∈A ca xva ≤ (Dv + R)zvv . The rounding
algorithm is essentially unchanged: we convert the trees obtained from xv into r-v paths, which are then
split into paths of regret at most R. Theorem 3.1 yields the following corollary.
Corollary 3.3 There is an LP-based 3-approximation for regret orienteering.
Integrality gaps for weaker LPs. Recall that in sketching our rounding algorithm, we assumed at first
(for simplicity) that we know the node v on the optimum path that has maximum distance from the root,
and impose in our LP that x is a preflow under which the r
v connectivity is 1, and that x only visits
nodes u with Du ≤ Dv . We conclude this section by demonstrating that it is crucial to impose both these
constraints. First, consider the following LP relaxation that simply encodes that x is a preflow of value 1
but does not require that the r
v connectivity under x is 1 for any specific v ∈ V . As before, we have
variables zu for each u ∈ V denoting the r
u connectivity under x.
X
max
ρ(u)zu
(R-O2)
u∈V

s.t.



x(δ in (u) ≥ x δ out (u)

x δ in (S) ≥ zu
X
ca xa ≤ B
a∈A
out

x δ

∀u ∈ V
∀S ⊆ V, u ∈ S


(r) = 1

x, z ≥ 0.
The above LP has unbounded integrality gap. Consider the following instance where the budget B ≥ 1 is an
integer. We have the following metric over V ∪ {r} where V = {r0 , v1 , v2 , . . . , vB }: each vi is at distance
B from r, and the distance between any two distinct vi , vj is 1; r0 is at distance 1 from r and distance B − 1
from every vi . Let ρ(v) = 1 for all v ∈ V . An r-rooted path of length B may visit r0 and at most one other
node in V , so the optimum solution has value 2.
Consider the preflow x that sends 21 unit of flow along the path P1 = r → r0 → v1 → v2 → . . . → vB ,
and 21 unit of flow along the path P2 = r → r0 . Letting zv = 21 for all v ∈ V \ {r0 } and zr0 = 1, it is easy to
verify that (x, z) is a feasible solution to (R-O2) and has objective value B2 + 1. Thus, the integrality gap of
(R-O2) is unbounded. Now consider the modification of (R-O2), where we select some node v and impost
that the r
v connectivity under x is 1 (i.e., we add the constraint zv = 1), but do not require that x only
visits nodes u with Du ≤ Dv . This LP continues to have an unbounded integrality gap, since if v = r0 , the
above (x, z) continues to be a feasible solution to this LP.
In the context of LP (R-O)—where we avoid the need for guessing the maximum-distance node on the
optimum path by having a separate collection {xva }, {zuv } of variables for all v ∈ V —the above example
0
shows that it is important to impose constraints (2) and (4). In the absence of constraint (2), letting xr be
0
0
the preflow that sends 12 unit of flow each along P1 and P2 , and setting zrr0 = 1, zvr = 21 for all v ∈ V \ {r0 },
yields P
a feasible solution to the resulting LP (of value B2 +1). On the other hand, retaining (2), but weakening
(4) to v,a ca xva ≤ B also yields an unbounded integrality gap: letting xvB be the preflow that sends 21 unit
0
of flow along P1 , and xr be the preflow that sends 12 unit of flow along P2 (and setting the zuv s appropriately)
yields a feasible solution to the resulting LP (of value B2 + 1).
6

4

Point-to-point orienteering

We now consider the generalization of rooted orienteering, where we have a start node r and an end node
t, and we seek an r-t path with cost at most B that collects the maximum reward. We may assume that r
and t have 0 reward, i.e., ρ(r) = ρ(t) = 0. The main result of this section is a novel reduction showing that
point-to-point (P2P) orienteering problem can be reduced to regret orienteering losing a factor of at most 2
(Theorem 4.1). Combining this with our LP-approach for regret orienteering and Corollary 3.3, we obtain
an LP-relaxation for P2P-orienteering having integrality gap at most 6 (Section 4.1). We believe that the
insights gained from this reduction may find further application.
Theorem 4.1 An α-approximation algorithm for regret orienteering (where α ≥ 1) can be used to obtain a
2α-approximation algorithm for P2P-orienteering.

Proof : Let G = ({r, t} ∪ V, E), {cuv }, {ρ(u)}, B be an instance of P2P-orienteering. Our reduction
is simple. Let P ∗ be an optimal solution. We “guess” a node v ∈ P ∗ (which could be r or t) such that
Dv + cvt = maxu∈P ∗ (Du + cut ). (That is, we enumerate over all choices for v.) Let S = {u ∈ {r, t} ∪ V :
Du + cut ≤ Dv + cvt }. We then consider two regret orienteering problems, both of which have regret bound
R = B − Dv − cvt and involve only nodes in S (i.e., we equivalently set ρ(u) = 0 for all u ∈
/ S); the
first problem has root r, and the second has root t. Let P1 and P2 be the solutions obtained for these two
problems respectively by our α-approximation algorithm. So for some u1 , u2 ∈ S, P1 is an r-u1 path, and
P2 may be viewed as a u2 -t path. Notice that P1 appended with the edge u1 t yields an r-t path of cost at
most Du1 + creg (P1 ) + cu1 t ≤ Du1 + cu1 t + B − Dv − cvt ≤ B, since u1 ∈ S. Similarly P2 appended with
the edge ru2 yields an r-t path of cost at most B. We return P1 + u1 t or ru2 + P2 , whichever has higher
reward.
To analyze this, we observe that the r-v portion of P ∗ is a feasible solution to the regret-orienteering
instance with root r, since its cost is at most B − cvt , and hence, its regret is at most R. Similarly, the
v-t portion of P∗ (viewed in reverse) is a feasible solution to the regret-orienteering instance with root t.
Therefore, max ρ(P1 + u1 t), ρ(ru2 + P2 )} ≥ ρ(P ∗ )/2α.

4.1

LP-relaxation for P2P-orienteering and rounding algorithm

As in the case of rooted orienteering, we replace the “guessing” step by having an indicator variables zvv
to denote if v is the node with maximum Dv + cvt on the optimum path. As suggested by the proof of
Theorem 4.1, our LP then incorporates ideas from the rooted-orienteering LP (R-O) to encode that, our
solution is, to an extent of zvv , a combination of r-v and v-t paths of regret at most B − Dv − cvt , with
respect to roots r and t respectively, that only visit nodes u with Du + cut ≤ Dv + cvt . (We get some
notational savings since we do not need to “guess” the endpoints of the desired regret-R paths: v is the
endpoint of both paths, and so we may work with r-v and v-t flows, instead of preflows.)
Let D = (V 0 := {r, t} ∪ V, A) denote the bidirected version of G. (Again, both (u, v) and (v, u) get
cost cuv .) For every v ∈ V 0 , we let xrv denotean r-v flow of value zvv , and xvt denote a v-t flow of value
zvv . We impose that xrv δ in (u) = xvt δ in (u) = 0 whenever Du + cut > Dv + cvt . We use zurv and zuvt
to denote respectively the r
u connectivity under xrv and the v
u connectivity under xvt . So in an
integral solution. zurv and zuvt indicate respectively if u lies on the r-v portion or on the v-t portion of the

7

optimum path. For nodes v, p, q ∈ V 0 and κ ≥ 0, define





out
Fv (p, q, κ) := x ∈ RA
(p) = κ = x δ in (q) ,
x δ in (p) = 0 = x δ out (q)
+ : x δ


x δ in (w) − x δ out (w) = 0
∀w ∈ V 0 \ {p, q}


in
0
x δ (w) = 0
∀w ∈ V : Dw + cwt > Dv + cvt
Note that if κ > 0, then F(u, u, κ) = ∅ for every u. Recall that ρ(r) = ρ(t) = 0.
X
max
ρ(u)(zurv + zuvt )
s.t.

u,v∈V 0
rv

x ∈ Fv (r, v, zvv ), xvt ∈ Fv (v, t, zvv )

xrv δ in (S) ≥ zurv

xvt δ in (S) ≥ zuvt
X
vt
v
ca (xrv
a + xa ) ≤ Bzv

(P2P-O)

∀v ∈ V 0
∀v ∈ V 0 , S ⊆ V 0 \ {r}, u ∈ S

(8)

∀v ∈ V 0 , S ⊆ V 0 \ {v}, u ∈ S

(9)

∀v ∈ V 0

(10)

a∈A

X
v∈V

zvv = 1,

x, z ≥ 0.

0

As before, we can model the cut constraints (8), (9) using additional flow variables and constraints to obtain
a compact formulation.
As with (R-O), the constraints of (P2P-O) imply that zurv = zuvt = 0 if Du + cut > Dv + cvt , and
rv
zu , zuvt ≤ zvv for all u. We remark that we could further add the constraint zurv + zuvt ≤ zvv for u, v ∈ V 0
to obtain a stronger relaxation whose integer solutions correspond to feasible point-to-point orienteering
solutions of the same cost. But we omit this since we do not need it in our rounding procedure. Let (x∗ , z ∗ )
be an optimal solution to (P2P-O) and OPT be its value.
Theorem 4.2 We can round (x∗ , z ∗ ) to a solution to P2P-orienteering of value at least OPT /6.
Proof : Consider some v ∈ V 0 . Let Rv = B − Dv − cvt be the regret bound that we require for the r-v
and v-t paths with respect to roots r and t respectively. Let Sv = {u ∈ V 0 : Du + cut ≤ Dv + cvt } be
the set of nodes that these paths may visit. It is easy to see via flow decomposition that cT xrv ≥ Dv zvv and
cT xvt ≥ cvt zvv . Therefore, (10) implies that cT xrv ≤ (Dv + Rv )zvv and cT xvt ≤ (cvt + Rv )zvv .
We can apply the rounding procedure in the proof of Theorem 3.1 to the flow xrv to P
obtain an r-rooted

rv
v
path ending at some node w ∈ Sv having regret at most Rv , and gathering reward at least
u∈V 0 ρ(u)zu /3zv
(see (6), (7)). Appending the edge wt to this path, we obtain an r-t path, which we denote Qrv , of c-cost at
most Rv + Dw + cwt ≤ B.
vt
tv
We can apply the same process to the xvt flow. In particular, let xtv
uw = xwu . Then, xP is a t-v flow
of value zvv with c-cost at most (cvt + Rv )zvv (as c is symmetric) and gathering reward u∈V ρ(u)zuvt .
Therefore, we find a t-rooted path
w ∈ Sv having regret at most Rv with respect to
 node
Pending at some
vt
v
t and gathering reward at least
u∈V 0 ρ(u)zu /3zv . Viewing this path as a w-t path and appending the
edge rw, we obtain an r-t path, which we denote Qvt , of c-cost at most Rv + cwt + Dw ≤ B.
We return the maximum-reward path among the collection {Qrv , Qvt : v ∈ V 0 }. The reward of this
path is at least

P

P
rv
vt
v ρ(Qrv ) + ρ(Qvt )
0 ρ(u) zu + zu
z
0
v,u∈V
v
v∈V
P
≥
= OPT /6.
2 v∈V 0 zvv
6

8

5

Compact LPs and improved guarantees for RVRP

Recall that in the regret-bounded vehicle routing problem (RVRP), we are given an undirected complete
graph G = ({r} ∪ V, E) on n nodes with a distinguished root (depot) node r, metric edge costs or distances
{cuv }, and a regret-bound R. The goal is to find the minimum number of rooted paths that cover all nodes so
that the regret of each node with respect to the path covering it is at most R. Throughout, let O∗ denote the
optimal value of the RVRP instance. We describe two compact LP-relaxations for RVRP and corresponding
rounding algorithms that yield improvements, in both approximation ratio and running time, over the RVRPalgorithm in [14]. In Section 5.1, we observe that the compact LP for orienteering (R-O) yields a natural
LP for RVRP; by combining the rounding ideas used for orienteering and Theorem 2.2, we obtain a 27approximation algorithm for RVRP. In Section 5.2, we formulate an unorthodox, stronger LP-relaxation
(R2) for RVRP by leveraging some key structural insights in [14]. We devise a rounding algorithm for
this LP that leads to a 15-approximation algorithm for RVRP, which is a significant improvement over the
guarantee obtained in [14].

5.1

Extending the orienteering LP to RVRP

The LP-relaxation below can be viewed as a natural variant of the orienteering LP adapted to RVRP. As
before, let D = ({r} ∪ V, A) be the bidirected version of G. For each node v, xv is a preflow (constraint
(11)) of value zvv such that the r
u connectivity under capacities {xva } is at least zuv for all u, v (constraint
(12)).
X
min
zvv
(R1)
s.t.

v

v
in



x (δ (u) ≥ xv δ out (u)

xv δ in (S) ≥ zuv
X
ca xva ≤ (Dv + R)zvv

∀u, v ∈ V

(11)

∀v ∈ V, S ⊆ V, u ∈ S

(12)

∀v ∈ V

a∈A


x δ out (r) = zvv
v

X

∀v ∈ V,

zuv ≥ 1

∀u ∈ V,

x, z ≥ 0.

v∈V

As before, we can obtain a compact formulation by replacing the cut constraints (12) with constraints involving suitable flow variables. Let (x∗ , z ∗ ) be an optimal solution to (R1), and OPT be its objective value.
Note that dOPT e ≤ O∗ .
Theorem 5.1 We can round (x∗ , z ∗ ) to obtain a 27-approximation for RVRP.
Proof : Apply Theorem 2.3 to each preflow x∗v taking K = zvv , to decompose x∗v into r-rooted
P outv
arborescences,
which
as rooted trees. This
weights {γT }T ∈T such that T γTv =
P v
Pwe view
Pyields nonnegative
v
u
v
v
v
zv , T γT c(T ) = a ca xa ≤ (Dv + R)zv , and T :u∈T γT ≥ zv for all u ∈ V . Note that v ∈ T whenever
γTv > 0. Doubling the edges not lying on the r-v paths of these trees
S and shortcutting, gives a collection
Pv of simple r-v paths having total regret at most 2R · zvv . Thus, v∈V Pv is a collection of rooted paths
covering each u ∈ V to an extent of 1 and having total regret cost at most 2R · OPT . Applying Theorem 2.2 with δ = 13 to this collection yields an RVRP solution with at most 24 · OPT + d3 · OPT e ≤
24 · OPT + 3 dOPT e ≤ 27 · O∗ paths.

9

5.2

A new compact LP for RVRP leading to a 15-approximation

We now propose a different LP for RVRP, which leads to a much-improved 15-approximation for RVRP.
To motivate this LP, we first collect some facts from [14, 6] pertaining to the regret objective. By merging
all nodes at distance 0 from each other, we may assume that cuv > 0 for all u, v ∈ V ∪ {r}, and hence
Dv > 0 for all v ∈ V .
Definition 5.2 ([14]) Let P be a rooted path ending at w. Consider an edge (u, v) of P , where u precedes
v on P . We call this a red edge of P if there exist nodes x and y on the r-u portion and v-w portion of P
respectively such that Dx ≥ Dy ; otherwise, we call this a blue edge of P . For a node x ∈ P , let red(x, P )
denote the maximal subpath Q of P containing x consisting of only red edges (which might be the trivial
path {x}).
Note that the first edge of a rooted path P is always a blue edge. Call the collection
Lemma 5.3 ([6]) For any rooted path P , we have

P

e red on P

ce ≤ 23 creg (P ).

Lemma 5.4 ([14]) (i) Let u, v be nodes on a rooted path P such that u precedes v on P and red(u, P ) 6=
red(v, P ); then Du < Dv . (ii) If P 0 is obtained by shortcutting P so that it contains at most one node from
each red interval of P , then for every edge (x, y) of P 0 with x preceding y on P 0 , we have Dx < Dy .
We say that a node u on a rooted path of P is a sentinel of P if u is the first node of red(u, P ). Part
(ii) above shows that if we shortcut each path P of an optimal RVRP-solution past the non-sentinel nodes
of P , then we obtain a distance-increasing collection of paths. Moreover, part (i) implies that if x and y
are sentinels on P with x appearing before y, then maxu∈red(x,P ) Du < minu∈red(y,P ) Du . Finally, every
non-sentinel node is connected to the sentinel corresponding to its red interval via red edges, and Lemma 5.3
shows that the total (c-) cost of these edges at most 1.5R(optimal value).
Thus, we can view an RVRP-solution as a collection of distance-increasing rooted paths covering some
sentinel nodes S, and a low-cost way of connecting the nodes in V \ S to S. Our LP-relaxation searches
for
 the best such solution. Let D := {Dv : v ∈ V }. For every u ∈ V , define Du to be the collection
[d1 , d2 ] : d1 , d2 ∈ D, d1 ≤ Du ≤ d2 of (closed) intervals. We have variables xu,I,u for every node
u ∈ V and interval I = [d1 , d2 ] ∈ Du to indicate if u is a sentinel and d1 , d2 are the minimum and
maximum distances (from r) respectively of nodes in the red interval corresponding to u; we say that I is
u’s distance interval. We also have variables xu,I,v for v 6= u to indicate that v is connected to sentinel u
with distance interval I, and edge variables {ze }e∈E that encode these connections. Finally, we have flow
variables fr,u,I , fu,I,v,J , fu,I,t for all u, v ∈ V and I ∈ Du , J ∈ Dv that encode the distance-increasing
rooted paths on the sentinels, with t representing a fictitious sink. We include constraints that encode that
the distance intervals of sentinels lying on the same path are disjoint, and a non-sentinel v can be connected
to (u, I) only if Dv ∈ I. We obtain the following LP.

10

X

min

fr,u,I

(R2)

u∈V,I∈Du

X

s.t.

xu,I,v ≥ 1

∀v ∈ V

(13)

∀u, v ∈ V, I ∈ Du

(14)

∀v ∈ V, {v} ⊆ S ⊆ V

(15)

fv,J,u,I = xu,I,u

∀u ∈ V, I ∈ Du

(16)

fu,I,v,J + fu,I,t = xu,I,u

∀u ∈ V, I ∈ Du

(17)

u∈V,I∈Du

xu,I,v ≤ xu,I,u ,

xu,I,v = 0 if Dv ∈
/I
X

xu,I,v
z δ(S) ≥
u∈S,I∈D
/
u

X

fr,u,I +

v∈V,J∈Dv

X
v∈V,J∈Dv

∀u, v ∈ V, I ∈ Du , J ∈ Dv :

fu,I,v,J = 0
X

I ∩ J 6= ∅ or Dv ≤ Du
X

creg
uv fu,I,v,J ≤ R ·

u,v∈V,I∈Du ,J∈Dv

fr,u,I

(18)
(19)

u∈V,I∈Du

X

X

ce ze ≤ 1.5R ·

e∈E

fr,u,I

(20)

u∈V,I∈Du

x, z, f ≥ 0.
Constraint (13) encodes that every node v is either a sentinel or is connected to a sentinel; (14) ensures that if
v is assigned to (u, I), then u is indeed a sentinel with distance interval I and that Dv ∈ I. Constraints (15)
ensure that the ze s (fractionally) connect each non-sentinel v to the sentinel specified by the xu,I,v variables.
Constraints (16), (17) encode that each sentinel (u, I) lies on rooted paths, and (18) ensures that these paths
are distance increasing and moreover the distance intervals of the sentinels on the paths are disjoint. Finally,
letting k denote the number of paths used, (19), (20) encode that the total regret of the distance-increasing
paths is at most kR (note that creg
ru = 0 for all u), and the total cost of the edges used to connect non-sentinels
to sentinels is at most 1.5kR. As before, the cut constraints (15) can be equivalently stated using flows to
obtain a polynomial-size LP. Let (x∗ , z ∗ , f ∗ ) be an optimal solution to (R2) and OPT denote its objective
value. We have already argued that an optimal RVRP-solution yields an integer solution to (R2), so we
obtain the following.
Lemma 5.5 dOPT e is at most the optimal value, O∗ , of the RVRP instance.
We remark that an integer solution to (R2) need not correspond to an RVRP solution since constraints
(15) only ensure that non-sentinels are connected to sentinels, but not necessarily via paths. Nevertheless,
we show that we can round (x∗ , z ∗ , f ∗ ) to an RVRP-solution using at most 15 · dOPT e paths.
Our rounding algorithm proceeds in a similar fashion as the RVRP-algorithm in [14]; yet, we obtain
an improved approximation ratio since one can solve (R2) exactly whereas one can only obtain a (2 + )approximate solution to the configuration LP in [14]. Let θ ∈ (0, 1) be a parameter that we will set later. We
3R
first obtain a forest of c-cost at most 1−θ
· OPT such that every component Z contains a witness node v that
is assigned to an extent of at least θ to sentinels in Z. We argue that if we contract the components of F , then
the distance-increasing sentinel flow paths yield an acyclic flow that covers every contracted component to
an extent of at least θ. Hence,
and hence
 OPT using the integrality property of flows, we obtain an integral flow, R
a collection of at most
rooted paths, that covers every component and has cost at most θ · OPT .
θ
Next, we show that we can uncontract the components and attach the component-nodes to these rooted paths
11

6R
incurring an additional cost of at most 1−θ
· OPT . Finally, by applying Lemma 2.1, we obtain an RVRP

 OPT 
6
1
solution with at most 1−θ + θ OPT +
rooted paths. We now describe the algorithm in detail and
θ
analyze it.

P
A1. For S ⊆ V , define h(S) = 1 if u∈S,I∈Du x∗u,I,v < θ for all v ∈ S, and 0 otherwise. h is a downwardsmonotone cut-requirement function: if ∅ =
6 A ⊆ B, then h(A) ≥ h(B). Use the LP-relative 2-approximation
algorithm in [17] for {0, 1} downwards-monotone functions to obtain a forest F such that |δ(S) ∩ F | ≥ h(S)
for all S ⊆ V .
P
A2. For every component Z of F with r ∈
/ Z, pick a witness node w ∈ Z such that u∈Z,I∈Du x∗u,I,w ≥ θ. Let
σ(w) = {(u, I) : u ∈ Z, x∗u,I,w > 0}. Let W ⊆ V be the set of all such witness nodes.
A3. f ∗ is an r
t flow in an auxiliary graph having nodes r, t, and (u, I) for all u ∈ V, I ∈ Du , edges (r, (u, I)),
((u, I), t) for all u ∈ V, I ∈ Du , and edges ((u, I), (v, J)) for all u, v ∈ V, I ∈ Du , J ∈ Dv such that Du < Dv
and I ∩ J = ∅. Let {fP∗ }P ∈P be a path-decomposition of this flow. Modify
S each flow path P ∈ P as follows.
First, drop t from P . Shortcut P past the nodes in P that are not in {r} ∪ w∈W σ(w). The resulting path maps
naturally to a rooted
 path
Pin G (obtained by simply dropping the distance intervals), which we denote by π(P ).
Clearly, creg π(P ) ≤ ((u,I),(v,J))∈P creg
uv since shortcutting does not increase the regret cost.
A4. Let Q be the collection of rooted paths obtained by taking the paths {π(P ) : P ∈ P} and contracting the
components of F . Let H be the directed graph obtained by directing the paths in Q away from r. To avoid
notational clutter, for a component
Z of F , we use Z to also denote the corresponding contracted
P
P node in H. For
each Q ∈ Q, define yQ = P ∈P:π(P ) maps to Q fP∗ . Lemma 5.8 proves that H is acyclic and Q∈Q:Z∈Q yQ ≥ θ
for every component Z of F .


y
and
A5. Use the integrality property of flows to round the flow θQ Q∈Q to an integer flow of value k ≤ OPT
θ
regret-cost at most R
θ · OPT . Since H is acyclic, this yields rooted paths P̂1 , . . . , P̂k so that every component
Z of F lies on exactly one P̂i path.
A6. We map the P̂i s to rooted paths in G that cover V as follows. Consider a path P̂i . Let Z be a component lying
on P̂i , and u, v ∈ Z be the nodes where P̂i enters and leaves Z respectively. We add to P̂i a u-v path that covers
all nodes of Z obtained by doubling all edges of Z except those on the u-v path in Z and shortcutting. Let P̃i
be the rooted path in G obtained by doing this for all components lying on P̂i .
A7. Finally, we use Lemma 2.1 to convert P̃1 , . . . , P̃k to an RVRP-solution.

Analysis. We first bound the cost of the forest F obtained in step A1 in Lemma 5.6, which also yields
a bound on the additional cost incurred in step A6 to convert the P̂i s to the rooted paths P̃i s. Lemma 5.8
proves that H is acyclic, and that y covers each component of F to an extent of at least θ. Theorem 5.9
combines these ingredients to obtain the stated performance guarantee.
Lemma 5.6 The forest F obtained in step A1 satisfies c(F ) ≤

3R
1−θ

· OPT .

 P
Proof : If h(S) = 1, then we have z ∗ δ(S) ≥ u∈S,I∈D
x∗u,I,v ≥ 1 − θ for all v ∈ S due to (13), (15).
/
u

P
3R
∗
So the forest F has cost at most 2
e ce ze /(1 − θ) which is at most 1−θ · OPT (due to (20)).
Lemma 5.7 Let P ∈ P and Z be a component of F . Let w be the witness node of Z. Then the number of
nodes in π(P ) ∩ Z is equal to |P ∩ σ(w)| ≤ 1.
Proof : Suppose u be a node in π(P ) ∩ Z. Then, there is a unique I ∈ Du such that (u, I) ∈ P . It must be
that (u, I) ∈ σ(w), as otherwise, since (u, I) cannot be in σ(w0 ) for any other witness node w0 , we would
have shortcut P past (u, I). Conversely, if (u, I) ∈ P ∩ σ(w), then by construction, we have u ∈ π(P ).
Thus, the number of nodes in |π(P ) ∩ Z| is equal to |P ∩ σ(w)|.
12

Finally, we have |P ∩ σ(w)| ≤ 1 for any flow path P ∈ P and any w ∈ W , since if (u, I) ∈ P ∩ σ(w)
(u could be w) then Dw ∈ I and the distance intervals corresponding to nodes on P are disjoint.
Lemma 5.8 H is acyclic. For any component Z of F ,

P

Q∈Q:Z∈Q yQ

≥ θ.

Proof : Let Z 0 be a node of H, and w0 be the witness node of Z 0 . Give Z 0 the label Dw0 . We claim that
sorting the nodes of H in increasing order of their labels yields a topological ordering of H, showing that
H is acyclic. Let (Z1 , Z2 ) be an arc of H. Let w1 , w2 be the witness nodes corresponding to Z1 and Z2
respectively. Then there is a flow path P ∈ P and some edge (u1 , u2 ) of σ(P ) where u1 ∈ Z1 , u2 ∈ Z2 . So
there exist (u1 , I1 ) ∈ P ∩ σ(w1 ) and (u2 , I2 ) ∈ P ∩ σ(w2 ) such that (u2 , I2 ) appears after (u1 , I1 ) on P .
= ∅. This implies that P
Dw1 < Dw2 .
Then, Du1 < Du2 , Du1 , Dw1 ∈ I1 , Du2 , Dw2P∈ I2 , and I1 ∩ I2P
∗
Let w be the witness node of Z. We have Q∈Q:Z∈Q yQ = P ∈P:π(P )∩Z6=∅ fP = P ∈P:P ∩σ(w)6=∅ fP∗
where the last equality follows from Lemma 5.7. Since |P ∩ σ(w)| ≤ 1 for all P ∈ P, we have
X
X
X
X
fP∗ =
fP∗ =
x∗u,I,u ≥ θ.
P ∈P:P ∩σ(w)6=∅

(u,I)∈σ(w) P ∈P:(u,I)∈P

(u,I)∈σ(w)

The second equality above follows from (16) and since {fP∗ }P ∈P is a path decomposition of f ∗ .
Theorem 5.9 The above algorithm returns an RVRP-solution with at most
Thus, taking θ = 31 , we obtain at most 15 · O∗ paths.

1
6
1−θ + θ



OPT +

 OPT 
θ

paths.


6
+ 1θ R · OPT . This follows because the
Proof : The total regret of the paths P̃1 , . . . , P̃k is at most 1−θ
total regret of P̂1 , . . . , P̂k is at most Rθ · OPT , and the regret-cost of the path added for each component Z
is at most the regret-cost of the tour Y obtained by doubling all edges of Z, and creg (Y ) = c(Y ) = 2c(Z).
Combining this with Lemma 5.6 proves the claim. So applying Lemma 2.1 to P̃1 , . . . , P̃k yields the stated
bound, and for θ = 31 , this bound translates to 12 · OPT + d3 · OPT e ≤ 15 · O∗ .

6

Minimum-regret TSP-path

We now consider the minimum-regret TSP-path problem, wherein we have (as before), a complete graph
G = (V 0 , E), r, t ∈ V 0 , metric edge costs {cuv }, and we seek a minimum-regret r-t path that visits all
nodes. Observe that this is precisely the ATSP-path problem under the asymmetric regret metric creg . We
establish a tight bound of 2 on the integrality gap of the standard ATSP-path LP for the class of regretmetrics (induced by a symmetric metric). We consider the following LP for min-regret TSP path. Let
D = (V 0 , A) be the bidirected version of G. Let bt = 1 = −br and bv = 0 for all v ∈ V 0 \ {r, t}.
X


in
out
min
creg
(v) = bv ∀v ∈ V 0 , x ≥ 0
(R-TSP)
a xa s.t. x δ (v) − x δ
a∈A

x(δ in (S)) ≥ 1

∀∅ =
6 S ⊆ V \ {r}.

(21)

Clearly, (R-TSP) is no stronger than the LP where we impose indegree and outdegree constraints on the
nodes. In contrast to Theorem
6.1,
 for general asymmetric metrics, even this stronger LP is only known to

log n
have integrality gap O log log n [2, 13]. (The corresponding LP for ATSP has poly(log log n) integrality
gap [1].)

13

u1

u3

u2

u4

r

t

v1

v3

v2

v4

Figure 1: The graph G4 .

Theorem 6.1 The integrality gap of (R-TSP) is 2 for regret metrics, and we can obtain an ATSP-path
solution with creg -cost at most 2 · OPT R-TSP in polynomial time.
Proof : We first describe the rounding algorithm showing an integrality-gap upper bound of 2. It is convenient to consider the following weaker LP.
X
min
ca xa − Dt
s.t.
x is an r-preflow, (21), x ≥ 0.
(P)
a

LP (P) is weaker than (R-TSP) because if x is a feasible solution to (R-TSP) then it is clearly feasible to (P),
and

X
X
X

 X
out
in
creg
x
=
c
x
+
D
x
δ
(u)
−
x
δ
(u)
=
ca xa − Dt .
u,v
a
a
u
u,v
(u,v)∈A

a∈A

u∈V 0

a∈A

We show how to obtain an ATSP-path solution of creg -cost at most 2OPT P , thereby showing that (P), and
hence (R-TSP) has integrality gap at most 2.
Let x∗ be an optimum solution to (P). Since the r
v connectivity is 1 under x∗ , applying Theorem 2.3
∗
to x with K = 1, yields a collection of r-rooted out-arborescences, all of which span V 0 . As should
be routine by now, we view these arborescences as spanning trees in G, convert each spanning tree to an
r-t path via doubling and shortcutting, and return the path with the smallest creg -cost. The creg -cost of
the path obtained from tree T is at most 2 c(T ) − DT . The bound now follows because if {γT } are the
reg
nonnegative
weights obtained

 2.3 (which sum up to 1), the c -cost we obtain is at most
P
Pfrom Theorem
∗
T γT · 2 c(T ) − Dt = 2
a ca xa − Dt .
As noted earlier, this integrality gap upper bound of 2 can also be inferred from the result of [10], which
(in particular) shows that one can obtain a spanning tree of cost at most the min-cost Hamiltonian r-t path.
Lower bound of 2 on the integrality gap. We show a lower bound of 2 on the integrality gap even for
the stronger LP, where
we we additionally
impose indegree
and outdegree
constraints on the nodes:




 i.e., we
impose x δ out (r) = 1 = x δ in (t) = x δ in (v) = x δ out (v) for all v 6= r, t, and x δ in (r) = 0 =
x δ out (t) .
Consider the graph Gk = (Vk , Ek ) for a given value k ≥ 2 shown in Figure 1, which is the standard example showing integrality gap of 23 for the Held-Karp relaxation for symmetric TSP. Here, Vk =
S
{r, t, u1 , . . . , uk , v1 , . . . , vk } and Ek = {ru1 , rv1 , u1 v1 } ∪ {uk t, vk t, uk vk } ∪ ki=1 {ui ui+1 , vi vi+1 }. All
edges of Ek have cost 1 and c is the induced shortest-path metric.
It is well known that any r-t walk that visits all nodes has c-cost at least 3k, so since Dt = k + 1, the
optimal integer solution has creg -cost at least 2k −1. We exhibit a fractional solution of creg -cost k. Consider
the following fractional solution.

14

xr,u1 = xr,v1 = xuk ,t = xvk ,t = 21 ,
xu1 ,v1 = xv1 ,u1 = xuk ,vk = xvk ,uk =
)
xui ,ui+1 = xvi ,vi+1 = 43
∀i = 1, . . . , k − 1.
xui+1 ,ui = xvi+1 ,vi = 14

1
4

All other xa are set to 0. It is easy to verify that this is a feasible fractional solution (satisfying the indegree and outdegree constraints as well). Among the arcs a with xa > 0, arcs (u1 , v1 ), (v1 , u1 ), (uk , vk ),
and
uk ) have creg -cost 1, and arcs of the form (ui+1 , ui ) and (vi+1 , vi ) have creg -cost 2. So we have
P (vk ,reg
a∈A ca xa = k.

References
[1] N. Anari and S. Oveis Gharan. Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP. In Proceedings of FOCS, 2015.
[2] A. Asadpour, M. X. Goemans, A. Madry, S. Oveis Gharan, and A. Saberi. An O(log n/ log log n)approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of SODA,
2010.
[3] J. Bang-Jensen, A. Frank, and B. Jackson. Preserving and increasing local edge-connectivity in mixed
graphs. SIAM J. Discrete Math., 8(2):155–178, 1995.
[4] N. Bansal, A. Blum, S. Chawla, and A. Meyerson. Approximation algorithms for deadline-TSP and
vehicle routing with time windows. In 36th STOC, 2004.
[5] A. Blum, P. Chalasani, D. Coppersmith, B. Pulleyblank, P. Raghavan, and M. Sudan. The Minimum
Latency Problem. In 26th STOC, pages 163–171, 1994.
[6] A. Blum, S. Chawla, D. R. Karger, T. Lane, and A. Meyerson. Approximation algorithms for orienteering and discount-reward TSP. SICOMP, 37:653–670, 2007.
[7] A. Bock, E. Grant, J. Könemann, and L. Sanita. The school bus problem in trees. In Proceedings of
ISAAC, 2011.
[8] D. Chakrabarty and C. Swamy. Facility location with client latencies: linear-programming based
techniques for minimum-latency problems. In Mathematics of Operations Research, 41(3):865–883,
2016.
[9] M. Charikar and B. Raghavachari. The finite capacity dial-a-ride problem. In Proceedings of 39th
FOCS, pages 458–467, 1998.
[10] K. Chaudhuri, P. B. Godfrey, S. Rao, and K. Talwar. Paths, Trees and Minimum Latency Tours. In
Proceedings of 44th FOCS, pages 36–45, 2003.
[11] C. Chekuri, N. Korula, and M. Pál. Improved algorithms for orienteering and related problems. ACM
Transactions on Algorithms, 8(3), 2012.
[12] J. Fakcharoenphol, C. Harrelson, and S. Rao The k-traveling repairman problem. ACM Trans. on Alg.,
Vol 3, Issue 4, Article 40, 2007.

15

[13] Z. Friggstad, A. Gupta, and M. Singh. An improved integrality gap for asymmetric TSP paths. Mathematics of Operations Research, 41(3): 745–757, 2016.
[14] Z. Friggstad and C. Swamy. Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing. In Proceedings of STOC, pages 744–753, 2014.
Detailed version posted on CS arXiv, Nov 2013.
[15] Z. Friggstad and C. Swamy. Compact, provably-good LPs for orienteering and regret-bounded vehicle
routing. In Proceedings of IPCO, pages 199-211, 2017.
[16] N. Garg. Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In Proceedings of
the 37th STOC, pages 396–402, 2005.
[17] M. X. Goemans and D. P. Williamson Approximating minimum-cost graph problems with spanning
tree edges. Operations Research Letters 16:183–189, 1994.
[18] B. L. Golden, L. Levy, and R. Vohra. The orienteering problem. Naval Research Logistics, 34:307–
318, 1987.
[19] M. Haimovich and A. Kan. Bounds and heuristics for capacitated routing problems. Mathematics of
Operations Research, 10:527–542, 1985.
[20] J. Park and B. Kim. The school bus routing problem: A review. European Journal of Operational
Research, 202(2):311–319, 2010.
[21] I. Post and C. Swamy. Linear-programming based techniques for multi-vehicle minimum latency
problems. In Proceedings of 26th SODA, pages 512–531, 2015.
[22] M. Spada, M. Bierlaire, and T. Liebling. Decision-aiding methodology for the school bus routing and
scheduling problem. Transportation Sc., 39:477–490, 2005.
[23] P. Toth and D. Vigo, eds. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics
and Applications, Philadelphia, 2002.

16

