Regret-Bounded Vehicle Routing Approximation Algorithms
Approximation Algorithms for
Regret-Bounded Vehicle Routing and
Applications
Chaitanya Swamy
University of Waterloo
Joint work with Zachary Friggstad
University of Alberta
Vehicle routing problems (VRPs)
client
Typical setup: visit all clients via route(s) starting from depot
so as to minimize client delays: e.g., max client delay (TSP)
But this does not differentiate between clients close to the
depot and those far away from it
Nearer clients may face more delay than further-away clients
– source of dissatisfaction
starting depot
r
Metric space
Regret-bounded VRP
Adopt a more client-centric view: seek bounded client regret
client regret
measure of waiting time of a client relative to
its shortest-path distance from depot
r
client
starting depot
Metric space
Regret-bounded VRP
Adopt more client-centric view: ensure bounded client regret
client regret
measure of
waiting time of a client
relative to
its
shortest-path distance from depot
Two natural ways to measure regret:
–
additive regret
of
v = c
P
(v) – D
v
–
multiplicative regret
of
v = c
P
(v)
/
D
v
r
v
c
P
(v)
P
D
v
c
P
(v)
= time to reach v along P
D
v
(min. possible
waiting time of v)
client
starting depot
Metric space
Regret-bounded VRP
Two natural ways to measure regret:
–
additive regret
of
v = c
P
(v) – D
v
–
multiplicative regret
of
v = c
P
(v)
/
D
v
r
v
c
P
(v)
P
D
v
Two problems: Given regret bound
R
, find minimum no. of
paths rooted at
r
that cover all clients such that:
1.
additive regret of each node
≤ R
additive RVRP
2.
multiplicative regret of each node
≤ R
multiplicative RVRP
client
starting depot
Metric space
Both additive- and multiplicative- RVRP are NP-hard to
approximate to a factor better than 2.
Additive RVRP turns out to be more fundamental.
(
R
ECALL
:
Cover all nodes with the minimum no. of rooted
paths such that additive regret of each node
v
≤
R
.)
c
P
(v) – D
v
(where
v
lies on path
P
)
Algorithms and techniques developed for additive RVRP
also yield algorithms for:
•
multiplicative RVRP and other regret-based VRPs
•
other classical vehicle routing problems
In the rest of the talk:
•
regret
additive regret
,
RVRP
additive-RVRP
•
regret-related VRP
VRP under
additive regret
Main result
We devise an
O(
1
)-approx. algorithm for (additive) RVRP.
Our algorithm is based on
LP-rounding:
contrasts with our limited
understanding of LPs for VRPs (with TSP being the exception)
We write a set-cover style
configuration LP
(with path variables):
•
Previously
only
O(log n)
-approximation and integrality gap was
known – follows easily from set-cover analysis +
orienteering
Our main contribution:
we show how to exploit LP-structure and
round an LP-solution losing only a constant factor
One of the few results
showing how to leverage configuration LPs
(other such results are known for bin-packing, Santa Claus problem,
min-makespan scheduling, combinatorial auctions)
•
Near-optimal LP solution can be efficiently obtained:
orienteering
yields approximate separation oracle for dual LP
≈ 30
Other results
•
Using our algorithm for RVRP and/or our techniques,
we obtain:
–
O(log(R/(R-
1
))
-approx. for
multiplicative-RVRP
–
O(min{log D/log log D,OPT
LP
, log n})
-approx. for
distance-constrained VRP
: cover all nodes with
minimum no. of rooted paths s.t.
waiting time
c
P
(v)
of
each node
v
is
≤ D
;
i
mproves upon the previous-best
O(min{log D, log n})-guarantee (Nagarajan-Ravi)
–
O(k
2
)
-approx. for
k-RVRP
: use
k
paths to cover nodes
and minimize max-regret;
previous guarantees were only
for
k=
1
via min-excess path (Blum et al.)
also show that integrality gap of configuration LP is
k
Other results (contd.)
•
Also consider directed graphs.
–
Observe that one can replace regret (in objective or
constraint) by cost (in a different asymmetric metric)
–
Hence, known results give: (a)
O(log n)
-approx. for
RVRP
; (b)
O(k
2
log n)
-approx. for
k-RVRP
–
c
-approx. for RVRP
2c
-approx. for
ATSP
Related work
•
Additive-RVRP proposed in Operations Research
literature under the generic name “
schoolbus problem
”
•
Bock et al.
studied RVRP and k-RVRP, and design:
–
an
O(log n)
-approximation using set cover + orienteering
–
a
3
-approximation algorithm in tree metrics
–
a
12.5
-approximation for k-RVRP in tree metrics
•
Additive regret also studied by
Blum et al.
, who used
excess to denote regret. They used the
min-excess path
problem
to approximate orienteering.
•
Nagarajan-Ravi
studied distance-constrained VRP:
–
give an
O(min{log D, log n})-approx. (
D
=
distance bound)
–
2
-approximation in tree metrics
A useful transformation
Define
c
reg
u,v
:= D
u
+ c
uv
– D
v
for all
u, v
.
•
c
reg
is an
asymmetric metric
– call this the
regret metric
•
c
reg
r,v
= 0
for all
v
•
For any path
P
and any
v
P
,
c
reg
P
(v) = c
P
(v) – D
v
= regret of
v
along
P
So RVRP
minimize no. of rooted paths of
c
reg
-length at
most
R
that cover all nodes
distance-constrained VRP in asymmetric
c
reg
-metric
•
c
-length and
c
reg
-length of any cycle are equal
Building some intuition
r
Suppose that all nodes
were at the same
distance from
r
V
= nodes other than
r
Building some intuition
•
V
can be grouped into
k
paths, each of
c
reg
-cost = c-cost
≤
R
can partition
V
into
k
components of
total cost
≤
kR
r
Suppose that all nodes
were at the same
distance from
r
V
= nodes other than
r
Building some intuition
Suppose that all nodes
were at the same
distance from
r
V
= nodes other than
r
•
V
can be grouped into
k
paths, each of
c
reg
-cost = c-cost
≤
R
can partition
V
into
k
components of
total cost
≤
kR
by
doubling + shortcutting
, get
k
paths of total cost
≤
2kR
•
Attach each path to
r
(pick an end-node
v
, add
rv
edge) to get
a rooted path. Total
c
reg
-length of resulting paths
≤
2kR
r
Building some intuition
•
V
can be grouped into
k
paths, each of
c
reg
-cost = c-cost
≤
R
can partition
V
into
k
components of
total cost
≤
kR
by
doubling + shortcutting
, get
k
paths of total cost
≤
2kR
•
Attach each path to
r
(pick an end-node
v
, add
rv
edge) to get
a rooted path. Total
c
reg
-length of resulting paths
≤
2kR
•
Break each resulting rooted path into segments of
c
reg
-length
≤
R
and attach each segment to
r
(this does not increase regret)
•
This gives
≤
3k
rooted paths covering
V
, each of
c
reg
-length
≤
R
.
r
Suppose that all nodes
were at the same
distance from
r
V
= nodes other than
r
Lemma:
Given at most
ak
paths of total
c
reg
-cost at most
bkR
, we
can efficiently find at most
(a+b)k
paths, each of
c
reg
-cost
≤ R
.
Lemma:
Given at most
ak
paths of total
c
reg
-cost at most
bkR
, we
can efficiently find at most
(a+b)k
paths, each of
c
reg
-cost
≤ R
.
So, suffices to find
O(OPT)
paths of total
c
reg
-length
O(R.OPT)
.
Lemma (Blum et al.):
total
c
-cost of
red edges
on
P
≤ 1.5
c
reg
(P)
.
D
v
path P
Configuration LP
Let
C
(R)
= {rooted paths P
:
c
reg
P
(v) = c
P
(v) – D
v
≤ R
for all
v
P
}
Minimize
∑
P
C
(R)
x
P
s.t.
∑
P
C
(R): v
P
x
P
≥
1
v
V
,
x ≥ 0
Dual separation problem
is an orienteering problem
There is a
(2+
)
-approximation for orienteering (
Chekuri et al.
)
This yields an approximate separation oracle, so a
(2+
)
-approx.
solution
x
*
to the configuration LP can be computed efficiently.
Let
k
*
=
∑
P
C
(R)
x
*
P
.
Rounding the LP solution x
*
Easy case:
suppose that directing edges of all paths
P
such
that
x
*
P
>0
away from
r
gives an acyclic graph
Then
x
*
is (the path-decomposition of) an acyclic flow of
value
k
*
and
c
reg
-cost
≤
k
*
R
that covers every node
Integrality of flows + acyclicity
can find
k
*
paths of
total
c
reg
-cost
≤
k
*
R
that cover all nodes
Rounding the LP solution x
*
Of course,
x
*
need not yield an acyclic flow.
Form a set
W
of
witness nodes
, partition
V\W
into components:
1.
Suitably shortcutting paths
P
with
x
*
P
>0
yields an
acyclic flow
–
that covers every node in
W
to an extent of at least 0.5
–
has value at most
k
*
and
c
reg
-cost at most
k
*
R
can obtain
O(k
*
)
paths covering
W
of total
c
reg
-cost
O(k
*
R)
2.
The total (
c
-)
cost
of all components is
O(k
*
R)
, and
every component contains
r
or some
witness node
we can attach the
V\W
to the paths found in step
1
incurring
O(k
*
R)
total additional regret (and cost)
So overall, obtain
O(k
*
)
paths with total regret
≤ O(k
*
R)
Rounding the LP solution x
*
Of course,
x
*
need not yield an acyclic flow.
Form a set
W
of
witness nodes
, partition
V\W
into components:
1.
Shortcutting paths
P
with
x
*
P
>0
yields a suitable
acyclic flow
that covers each node in
W
to an extent of at least 0.5
2.
The total (
c
-)
cost
of all components is
O(k
*
R)
, and
every component contains
r
or some
witness node
–
Form components whose
cost can be charged to the
red edges
of the paths
in the support of
x
*
–
Can be done cleanly by setting up a network design problem
with a
downwards-monotone cut-requirement function
–
Also ensures that each component contains a node with large
incoming flow on blue edges, which becomes a witness node
Rounding the LP solution x
*
Of course,
x
*
need not yield an acyclic flow.
Form a set
W
of
witness nodes
, partition
V\W
into components:
1.
Shortcutting paths
P
with
x
*
P
>0
yields a suitable
acyclic flow
that covers each node in
W
to an extent of at least 0.5
2.
The total (
c
-)
cost
of all components is
O(k
*
R)
, and
every component contains
r
or some
witness node
–
Form components whose
cost can be charged to the
red edges
of the paths
in the support of
x
*
Idea: pick edges to cover all sets
S
s.t.
∑
P: red(P)
(S)≠
x
*
P
≥ 0.5
(
x
*
fractional solution of cost
O(k
*
R)
that covers all such
S
)
Do not know how to do this
Rounding the LP solution x
*
Of course,
x
*
need not yield an acyclic flow.
Form a set
W
of
witness nodes
, partition
V\W
into components:
1.
Shortcutting paths
P
with
x
*
P
>0
yields a suitable
acyclic flow
that covers each node in
W
to an extent of at least 0.5
2.
The total (
c
-)
cost
of all components is
O(k
*
R)
, and
every component contains
r
or some
witness node
–
Form components whose
cost can be charged to the
red edges
of the paths
in the support of
x
*
Idea: pick edges to cover all sets
S
s.t.
∑
P: red(P)
(S)≠
x
*
P
≥ 0.5
Settle for:
cover all sets
S
s.t.
v
S, ∑
P: red(P, v)
(S)≠
x
*
P
≥ 0.5
–
Can be done cleanly by setting up a network design problem
with a
downwards-monotone cut-requirement function
–
Also ensures that each component contains a node with large
incoming flow on blue edges, which becomes a witness node
Application to DVRP
R
ECALL Distance-constrained VRP (DVRP)
:
Cover all nodes with
min no. of rooted paths s.t. waiting time of each node
v
≤
D
.
c
P
(v)
(where
v
lies on path
P
)
Simple
O(log D)
-approximation using RVRP
D
v
D
Application to DVRP
R
ECALL Distance-constrained VRP (DVRP)
:
Cover all nodes with
min no. of rooted paths s.t. waiting time of each node
v
≤
D
.
c
P
(v)
(where
v
lies on path
P
)
Simple
O(log D)
-approximation using RVRP
D
v
D
0
-2
i-
1
-3
-7
-
1
-2
i
-D/2
Nodes
v
with
D
v
(
D-2
i
, D-2
i-
1
]
have regret
<
2
i
under OPT
can cover these using
O(OPT)
paths, each of regret
≤ 2
i-
1
waiting time of each such
v ≤ D
O(log D)
intervals
O(log D)
-approximation
Application to DVRP
Improved
O
(
)
-approximation using RVRP
Let
N
*
i
= no. of paths of OPT having regret
< 2
i
F
i
= no. of (feasible) paths we use to cover
S
i
D
v
D
0
-2
i-
1
-3
-7
-
1
-2
i
-D/2
For any
k<i
, can cover
S
i
using
F
k
+ O(N
*
k
+2
i-k
(N
*
i
–
N
*
k
))
paths
So
F
i
≤ min
0≤k<i
[F
k
+ O(N
*
k
+2
i-k
(N
*
i
–
N
*
k
))]
Base case
F
0
≤ N
*
0
recurrence solves to give
F
i
= O(i/log i) N
*
i
i
goes up to
log D
get O(log D/log log D)
-approximation
These paths cover
S
i
= {v: Dv
>
D-2
i
}
(#)
S
i
Conclusions and open questions
•
We systematically study regret-bounded VRPs
–
devise a constant-approx. for additive-RVRP
–
novel rounding method for the configuration LP; new ideas
to deal with regret
–
this yields bounds for various other RVRPs, as well as
distance-constrained VRP (DVRP)
•
Is there an
O(
1
)
-approx. for DVRP?
–
our work is a promising step: improves upon the usual log-
guarantee given by set cover, but we use additive-RVRP as a
black box; better way of leveraging underlying ideas
•
Improve upon the
O(k
2
)
-approximation for k-RVRP.
•
What about other regret-based objectives: e.g., minimizing
sum of regrets (much stronger than minimizing latency)?
Thank You.
Regret-bounded vehicle routing problems aim to minimize client delays by considering client-centric views and bounded client regret measures. This involves measuring waiting times relative to shortest-path distances from the starting depot. Additive and multiplicative regret measures are used to address the fundamental challenges in regret-bounded VRPs, with algorithms developed for both types of regret. An O(1)-approximation algorithm for additive regret-bounded VRP has been devised based on LP-rounding techniques.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications Chaitanya Swamy University of Waterloo Joint work with Zachary Friggstad University of Alberta
Vehicle routing problems (VRPs) Metric space starting depot r client Typical setup: visit all clients via route(s) starting from depot so as to minimize client delays: e.g., max client delay (TSP) But this does not differentiate between clients close to the depot and those far away from it Nearer clients may face more delay than further-away clients source of dissatisfaction
Regret-bounded VRP Metric space starting depot r client Adopt a more client-centric view: seek bounded client regret client regret measure of waiting time of a client relative to its shortest-path distance from depot
Regret-bounded VRP cP(v) Metric space r starting depot P client v Dv cP(v) = time to reach v along P Adopt more client-centric view: ensure bounded client regret client regret measure of waiting time of a client relative to its shortest-path distance from depot Dv (min. possible waiting time of v) Two natural ways to measure regret: additive regret of v = cP(v) Dv multiplicative regret of v = cP(v)/Dv
Regret-bounded VRP cP(v) Metric space r starting depot P client v Dv Two natural ways to measure regret: additive regret of v = cP(v) Dv multiplicative regret of v = cP(v)/Dv Two problems: Given regret bound R, find minimum no. of paths rooted at r that cover all clients such that: 1. additive regret of each node R 2. multiplicative regret of each node R multiplicative RVRP additive RVRP
Both additive- and multiplicative- RVRP are NP-hard to approximate to a factor better than 2. Additive RVRP turns out to be more fundamental. (RECALL: Cover all nodes with the minimum no. of rooted paths such that additive regret of each node v R.) cP(v) Dv (where v lies on path P) Algorithms and techniques developed for additive RVRP also yield algorithms for: multiplicative RVRP and other regret-based VRPs other classical vehicle routing problems In the rest of the talk: regret additive regret, regret-related VRP VRP under additive regret RVRP additive-RVRP
Main result 30 We devise an O(1)-approx. algorithm for (additive) RVRP. Our algorithm is based on LP-rounding: contrasts with our limited understanding of LPs for VRPs (with TSP being the exception) We write a set-cover style configuration LP (with path variables): Previously only O(log n)-approximation and integrality gap was known follows easily from set-cover analysis + orienteering Our main contribution: we show how to exploit LP-structure and round an LP-solution losing only a constant factor One of the few results showing how to leverage configuration LPs (other such results are known for bin-packing, Santa Claus problem, min-makespan scheduling, combinatorial auctions) Near-optimal LP solution can be efficiently obtained: orienteering yields approximate separation oracle for dual LP
Other results Using our algorithm for RVRP and/or our techniques, we obtain: O(log(R/(R-1))-approx. for multiplicative-RVRP O(min{log D/log log D,OPTLP, log n})-approx. for distance-constrained VRP: cover all nodes with minimum no. of rooted paths s.t. waiting time cP(v) of each node v is D; improves upon the previous-best O(min{log D, log n})-guarantee (Nagarajan-Ravi) O(k2)-approx. for k-RVRP: use k paths to cover nodes and minimize max-regret; previous guarantees were only for k=1 via min-excess path (Blum et al.) also show that integrality gap of configuration LP is k
Other results (contd.) Also consider directed graphs. Observe that one can replace regret (in objective or constraint) by cost (in a different asymmetric metric) Hence, known results give: (a) O(log n)-approx. for RVRP; (b) O(k2 log n)-approx. for k-RVRP c-approx. for RVRP 2c-approx. for ATSP
Related work Additive-RVRP proposed in Operations Research literature under the generic name schoolbus problem Bock et al. studied RVRP and k-RVRP, and design: an O(log n)-approximation using set cover + orienteering a 3-approximation algorithm in tree metrics a 12.5-approximation for k-RVRP in tree metrics Additive regret also studied by Blum et al., who used excess to denote regret. They used the min-excess path problem to approximate orienteering. Nagarajan-Ravi studied distance-constrained VRP: give an O(min{log D, log n})-approx. (D=distance bound) 2-approximation in tree metrics
A useful transformation Define cregu,v := Du + cuv Dv for all u, v. creg is an asymmetric metric call this the regret metric cregr,v = 0 for all v For any path P and any v P, cregP(v) = cP(v) Dv = regret of v along P So RVRP minimize no. of rooted paths of creg-length at most R that cover all nodes distance-constrained VRP in asymmetric creg-metric c-length and creg-length of any cycle are equal
Building some intuition Suppose that all nodes were at the same distance from r V = nodes other than r r
Building some intuition Suppose that all nodes were at the same distance from r V = nodes other than r r V can be grouped into k paths, each of creg-cost = c-cost R can partition V into k components of total cost kR
Building some intuition Suppose that all nodes were at the same distance from r V = nodes other than r r V can be grouped into k paths, each of creg-cost = c-cost R can partition V into k components of total cost kR by doubling + shortcutting, get k paths of total cost 2kR Attach each path to r (pick an end-node v, add rv edge) to get a rooted path. Total creg-length of resulting paths 2kR
Building some intuition Suppose that all nodes were at the same distance from r V = nodes other than r r V can be grouped into k paths, each of creg-cost = c-cost R can partition V into k components of total cost kR by doubling + shortcutting, get k paths of total cost 2kR Attach each path to r (pick an end-node v, add rv edge) to get a rooted path. Total creg-length of resulting paths 2kR Break each resulting rooted path into segments of creg-length R and attach each segment to r (this does not increase regret) This gives 3k rooted paths covering V, each of creg-length R.
Lemma: Given at most ak paths of total creg-cost at most bkR, we can efficiently find at most (a+b)k paths, each of creg-cost R.
Lemma: Given at most ak paths of total creg-cost at most bkR, we can efficiently find at most (a+b)k paths, each of creg-cost R. So, suffices to find O(OPT) paths of total creg-length O(R.OPT). path P Dv Lemma (Blum et al.): total c-cost of red edges on P 1.5creg(P).
Configuration LP Let C(R) = {rooted paths P: cregP(v) = cP(v) Dv R for all v P} Minimize P C(R) xP s.t. P C(R): v P xP 1 v V, x 0 Dual separation problem is an orienteering problem There is a (2+ )-approximation for orienteering (Chekuri et al.) This yields an approximate separation oracle, so a (2+ )-approx. solution x* to the configuration LP can be computed efficiently. Let k* = P C(R) x*P .
Rounding the LP solution x* Easy case: suppose that directing edges of all paths P such that x*P>0 away from r gives an acyclic graph Then x* is (the path-decomposition of) an acyclic flow of value k* and creg-cost k*R that covers every node Integrality of flows + acyclicity can find k* paths of total creg-cost k*R that cover all nodes
Rounding the LP solution x* Of course, x* need not yield an acyclic flow. Form a set W of witness nodes, partition V\W into components: 1. Suitably shortcutting paths P with x*P>0 yields an acyclic flow that covers every node in W to an extent of at least 0.5 has value at most k* and creg-cost at most k*R can obtain O(k*) paths covering W of total creg-cost O(k*R) 2. The total (c-)cost of all components is O(k*R), and every component contains r or some witness node we can attach the V\W to the paths found in step 1 incurring O(k*R) total additional regret (and cost) So overall, obtain O(k*) paths with total regret O(k*R)
Rounding the LP solution x* Of course, x* need not yield an acyclic flow. Form a set W of witness nodes, partition V\W into components: 1. Shortcutting paths P with x*P>0 yields a suitable acyclic flow that covers each node in W to an extent of at least 0.5 2. The total (c-)cost of all components is O(k*R), and every component contains r or some witness node Form components whose cost can be charged to the red edges of the paths in the support of x* Can be done cleanly by setting up a network design problem with a downwards-monotone cut-requirement function Also ensures that each component contains a node with large incoming flow on blue edges, which becomes a witness node
Rounding the LP solution x* Of course, x* need not yield an acyclic flow. Form a set W of witness nodes, partition V\W into components: 1. Shortcutting paths P with x*P>0 yields a suitable acyclic flow that covers each node in W to an extent of at least 0.5 2. The total (c-)cost of all components is O(k*R), and every component contains r or some witness node Form components whose cost can be charged to the red edges of the paths in the support of x* Idea: pick edges to cover all sets S s.t. P: red(P) (S) x*P 0.5 (x* fractional solution of cost O(k*R) that covers all such S) Do not know how to do this
Rounding the LP solution x* Of course, x* need not yield an acyclic flow. Form a set W of witness nodes, partition V\W into components: 1. Shortcutting paths P with x*P>0 yields a suitable acyclic flow that covers each node in W to an extent of at least 0.5 2. The total (c-)cost of all components is O(k*R), and every component contains r or some witness node Form components whose cost can be charged to the red edges of the paths in the support of x* Idea: pick edges to cover all sets S s.t. P: red(P) (S) x*P 0.5 Settle for: cover all sets S s.t. v S, P: red(P, v) (S) x*P 0.5 Can be done cleanly by setting up a network design problem with a downwards-monotone cut-requirement function Also ensures that each component contains a node with large incoming flow on blue edges, which becomes a witness node
Application to DVRP RECALL Distance-constrained VRP (DVRP): Cover all nodes with min no. of rooted paths s.t. waiting time of each node v D. cP(v)(where v lies on path P) Simple O(log D)-approximation using RVRP Dv D
Application to DVRP RECALL Distance-constrained VRP (DVRP): Cover all nodes with min no. of rooted paths s.t. waiting time of each node v D. cP(v)(where v lies on path P) Simple O(log D)-approximation using RVRP -7 -1 Dv -3 D 0 -2i -2i-1 -D/2 Nodes v with Dv (D-2i, D-2i-1] have regret <2i under OPT can cover these using O(OPT) paths, each of regret 2i-1 waiting time of each such v D O(log D) intervals O(log D)-approximation
Application to DVRP log D Improved O()-approximation using RVRP log log D These paths cover Si = {v: Dv >D-2i} (#) Let N*i = no. of paths of OPT having regret < 2i Fi = no. of (feasible) paths we use to cover Si Si -7 -1 Dv -3 D 0 -2i -2i-1 -D/2 For any k<i, can cover Si using Fk + O(N*k+2i-k(N*i N*k)) paths So Fi min0 k<i [Fk+ O(N*k+2i-k(N*i N*k))] Base case F0 N*0 recurrence solves to give Fi = O(i/log i) N*i i goes up to log D get O(log D/log log D)-approximation
Conclusions and open questions We systematically study regret-bounded VRPs devise a constant-approx. for additive-RVRP novel rounding method for the configuration LP; new ideas to deal with regret this yields bounds for various other RVRPs, as well as distance-constrained VRP (DVRP) Is there an O(1)-approx. for DVRP? our work is a promising step: improves upon the usual log- guarantee given by set cover, but we use additive-RVRP as a black box; better way of leveraging underlying ideas Improve upon the O(k2)-approximation for k-RVRP. What about other regret-based objectives: e.g., minimizing sum of regrets (much stronger than minimizing latency)?
