arXiv:1511.07412v1 [] 23 Nov 2015

Approximation Algorithms for Route Planning with Nonlinear Objectives
Ger Yang

Evdokia Nikolova

Electrical and Computer Engineering
University of Texas at Austin
geryang@utexas.edu

Electrical and Computer Engineering
University of Texas at Austin
nikolova@austin.utexas.edu

Abstract
We consider optimal route planning when the objective function is a general nonlinear and non-monotonic function. Such
an objective models user behavior more accurately, for example, when a user is risk-averse, or the utility function needs
to capture a penalty for early arrival. It is known that as
nonlinearity arises, the problem becomes NP-hard and little
is known about computing optimal solutions when in addition there is no monotonicity guarantee. We show that an approximately optimal non-simple path can be efficiently computed under some natural constraints. In particular, we provide a fully polynomial approximation scheme under hop
constraints. Our approximation algorithm can extend to run
in pseudo-polynomial time under a more general linear constraint that sometimes is useful. As a by-product, we show
that our algorithm can be applied to the problem of finding a
path that is most likely to be on time for a given deadline.

Introduction
In this paper, we present approximation algorithms for route
planning with a nonlinear objective function. Traditionally, route planning problems are modeled as linear shortest
path problems and there are numerous algorithms, such as
Bellman-Ford or Dijkstra’s algorithm, that are able to find
the optimal paths efficiently. However, nonlinearity arises
when we would like to make more complicated decisionmaking rules. For example, in road networks, the objective
might be a nonlinear function that represents the trade-off
between traveling time and cost. Unfortunately, dynamic
programming techniques used in linear shortest path algorithms no longer apply as when nonlinearity appears, subpaths of optimal paths may no longer be optimal.
Applications include risk-averse routing or routing
with a nonlinear objective when we are uncertain about
the traffic conditions (Nikolova, Brand, and Karger 2006;
Nikolova et al. 2006). A risk-averse user tends to choose a
route based on both the speediness and reliability. Such riskaverse attitude can often be captured by a nonlinear objective, e.g. a mean-risk objective (Nikolova 2010). On the
other hand, the user might seek a path that maximizes the
probability for him to be on time given a deadline. This objective was considered by Nikolova (2010) to capture the
risk-averse behavior. For Gaussian travel times, the latter
paper only considered the case where at least one path has

mean travel time less than the deadline, and consequently the
objective function can be modeled as a monotonic function.
The problem of finding a path that minimizes a
monotonic increasing objective has been studied in
the literature (Goyal and Ravi 2013; Nikolova 2010;
Tsaggouris and Zaroliagis 2009). What if there is no
monotonicity guarantee? For example, consider the deadline problem when we know that all paths have mean
travel time longer than the deadline, or consider the
well-known cost-to-time ratio objective (Megiddo 1979;
Guérin and Orda 1999) in various combinatorial optimization problems. Without the monotonicity assumption,
the problem usually becomes very hard. It has been
shown (Nikolova, Brand, and Karger 2006) that for a
general objective function, finding the optimal simple
path is NP-hard. This is because such a problem often
involves finding the longest path for general graphs,
which is known to be a strongly NP-hard problem
(Karger, Motwani, and Ramkumar 1997), namely finding a
constant-factor approximation is also NP-hard. This suggests that for a very general class of functions, including the
cost-to-time ratio objective (Ahuja, Batra, and Gupta 1983),
not only is the problem itself NP-hard but so is also its
approximation counterpart.
Therefore, in this paper, we focus on the problem that accepts non-simple paths, in which it is allowed to visit nodes
more than once. To make this problem well-defined, we consider the problem under either a hop constraint or an additional linear constraint, where we say a path is of γ hops if it
contains γ edges. We design a fully polynomial approximation scheme under hop constraints, and show that the algorithm can extend to run in pseudo-polynomial time under an
additional linear constraint. Further, we show how our algorithm can be applied to the cost-to-time ratio objective and
the deadline problem.

Related Work
The route planning problem with nonlinear objective we
consider here is related to multi-criteria optimization (e.g.,
Papadimitriou and Yannakakis 2000). The solutions to these
problems typically look for approximate Pareto sets, namely
a short list of feasible solutions that provide a good approximation to any non-dominated or optimal solution. A fully
polynomial approximation scheme (FPTAS) for route plan-

ning with general monotonic and smoothed objective functions was presented by Tsaggouris and Zaroliagis (2009),
based on finding an approximate Pareto set for the feasible paths. Later, Mittal and Schulz (2013) provided a general
approach for monotonic and smoothed combinatorial optimization problems and showed how to reduce these problems to multi-criteria optimization.
A special class of nonlinear optimization is quasiconcave minimization. This class of problems has the
property that the optimal solution is an extreme point
of the feasible set (Horst, Pardalos, and Van Thoai 2000).
For quasi-concave combinatorial minimization problems,
Kelner and Nikolova (2007) proved (log n)-hardness of approximation and they also gave an additive approximation
algorithm for low-rank quasi-concave functions based on
smoothed analysis. Later, Nikolova (2010) presented an FPTAS for risk-averse quasi-concave objective functions. In recent work, Goyal and Ravi (2013) gave an FPTAS for general monotone and smooth quasi-concave functions.
Without assuming monotonicity, the problem was studied
by Nikolova, Brand, and Karger (2006), who proved hardness results and gave a pseudo-polynomial approximation
algorithm with integer edge weights for some specific objective functions.

Problem Statement and Preliminaries
Consider a directed graph G = (V, E). Denote the number
of vertices as |V | = n, and the number of edges as |E| = m.
Suppose we are given a source node s and a destination node
t. In the nonlinear objective shortest path problem, we seek
an s − t path p, possibly containing loops, that minimizes
some nonlinear objective function f (p).
More precisely, denote
S the feasible set of all s − t paths
by Pt , and let P = v∈V Pv be the set of paths that start
from s. Here we have not yet imposed assumptions that P
contains only simple paths. Let f : P → R+ be a given
objective function. Then we can write the problem as finding
the path p∗ that minimizes this objective function:
p∗ = arg min f (p)
p∈Pt

(1)

We assume that f is a low-rank nonlinear function with
some smoothness condition. Specifically, we say that f is
of rank d if there exists a function g : Rd+ → R+ and
an m × d weight matrix W = (we,k )m×d , with positive
P path p ∈ P, f (p) =
P that for any
P entries, such
g( e∈p we,1 , e∈p we,2 , . . . , e∈p we,d ).
We interpret this as having d criteria, such as for example
length in miles, cost, travel time, etc. so that each edge is
associated with d additive weights, where the k-th weight
for edge e is denoted by we,k . Then, the k-th weights of
all edges can be represented by the column vector wk =
(w1,k , w2,k , . . . , wm,k )T . For simplicity, we denote the sum
of
P the k-th weights of the edges along path p as lk (p) =
e∈p we,k , and we call it the k-th criterion of path p. Hence,
the objective function f can be rewritten as a function of all
criteria:
f (p) = g(l1 (p), l2 (p), . . . , ld (p))
(2)

Figure 1: Illustration of a path polytope on a doubly
weighted graph with a hop constraint. Each blue cross and
red dot correspond to an s − t path projected onto W. We
can use polynomially many red dots to approximate the path
polytope and consequently to approximate the optimal path.
Consider the linear space spanned by the d criteria W =
span(w1 , w2 , . . . , wd ). Then, each feasible s − t path p ∈
Pt has an associated point in this d-dimensional space W
given by l(p) = (l1 (p), l2 (p), . . . , ld (p)), providing the values of the d criteria for that path. We shall call the convex hull of such points the path polytope.1 We assume that
the weights matrix W contains only positive entries, and
thus the path polytope is bounded from below: for any path
p ∈ Pt and criterion k ∈ {1, . . . , d}, we have lk (p) ≥
minp′ ∈Pt lk (p′ ). This lower-bound corresponds to the shortest path with respect to the k-th criterion. For upper bounds
of the polytope, we defer the discussion to the later sections.
The size of the path polytope is in worst case exponential
in the problem size. The main idea of this paper is to approximate the path polytope with polynomially many paths,
as illustrated in Figure 1. As we will show in this paper, the
optimal path can be approximated if there are some smoothness conditions on the objective function. The smoothness
assumption we adapt here is as follows: g is assumed to be βLipschitz on the log-log scale with respect to the L1-norm:
that is, for any y, y′ in the path polytope,
| log g(y) − log g(y′ )| ≤ βk log y − log y′ k1

(3)

where log y is defined as a column vector: log y =
(log y1 , log y2 , . . . , log yd )T .
In this paper, we design approximation algorithms for this
problem, formally defined as follows:
Definition 1. An α-approximation algorithm for a minimization problem with optimal solution value OP T and
α > 1 is a polynomial-time algorithm that returns a solution of value at most αOP T .
1

Strictly speaking, it is the projection of the feasible path polytope in Rm onto this d-dimensional subspace but for simplicity we
will just call it the path polytope in this paper.

The best possible approximation algorithms provide solutions that are arbitrarily close to the optimal solution:
Definition 2. A fully-polynomial approximation scheme
(FPTAS) is an algorithm for an optimization problem that,
given desired accuracy ǫ > 0, finds in time polynomial in
1
′
ǫ and the input size, a solution of value OP T that satisfies
′
|OP T − OP T | ≤ ǫOP T , for any input, where OP T is the
optimal solution value.

Hardness Results
We can categorize the problem on general directed graphs
into two types: one is the problem that accepts only simple paths, by which we mean each vertex can only be visited once in any feasible path; the other is the problem
that accepts non-simple paths. Unfortunately, both types
of problems turn out to be hard. In fact, the problem that
only accepts simple paths in general involves finding the
longest simple path, which is strongly NP-hard, namely it
is NP-hard to approximate to within any constant factor
(Karger, Motwani, and Ramkumar 1997).
First, we present a natural objective function that has been
considered in the literature, that is hard to approximate.

Minimum Cost-to-Time Ratio Path Problem
The cost-to-time ratio objective function is a rank 2 function,
defined as follows:
X
 P
X
e∈p we,1
f (p) = g
we,1 ,
we,2 = P
e∈p we,2
e∈p
e∈p

For simplicity, we assume W has strictly positive entries. This objective function has been
considered
previously
for
different
combinatorial
optimization
problems
(Megiddo 1979;
Correa, Fernandes, and Wakabayashi 2010). However, finding the minimum cost-to-time ratio simple path is known
to be an NP-hard problem (Ahuja, Batra, and Gupta 1983).
Here, we show its hardness of approximation:
Theorem 1. There is no polynomial-time α-approximation
algorithm for the minimum cost-to-time ratio simple path
problem for any constant factor α, unless P = N P .

Proof. To facilitate the presentation of our hardness
of approximation proof, we first show that this problem is NP-hard. We reduce a longest path problem
instance to a minimum cost-to-time ratio simple path
problem instance. The longest path problem is known
to be NP-hard to approximate to within any constant
factor (Karger, Motwani, and Ramkumar 1997). First, we
choose some λ > 0. For an instance of the longest path
problem, which is some graph G with unweighted edges and
a designated source node s and sink node t, we create an instance of the minimum cost-to-time ratio path problem with
the same graph G, source s and sink t and the following
(cost,time) edge weights:
1. For each edge e incident to s, set we = (λn + 1, 1).
2. For the remaining edges e, set we = (1, 1).

We can see that a path is optimal under the ratio objective
if and only if it is the longest path with respect to the unweighted edges (or, equivalently, with respect to the second weight). This shows that the minimum cost-to-time ratio
simple path problem is NP-hard.
To show the hardness of approximation, similarly, we
use the fact that the longest path problem cannot be approximated to within any constant factor unless P = N P
(Karger, Motwani, and Ramkumar 1997). Suppose the contrary, namely that we can find a (1 + ǫ)-approximation algorithm for the minimum cost-to-time ratio simple path problem, for some ǫ ∈ (0, λ). To be precise, since we can choose
λ while ǫ comes from the assumed approximation algorithm,
we can set λ > ǫ. For a given instance of longest path, consider the corresponding instance of minimum cost-to-time
ratio path problem above. Let p∗ be the optimal min cost-totime ratio path. Then, the (1 + ǫ)-approximation algorithm
will return a simple path p such that
λn + l2 (p)
λn + l2 (p∗ )
≤ (1 + ǫ)
l2 (p)
l2 (p∗ )
Rearranging this, we get the inequality:
(λn − ǫl2 (p))l2 (p∗ ) ≤ λ(1 + ǫ)nl2 (p)
Since l2 (p) ≤ n and ǫ < λ, we get the following:
l2 (p∗ ) ≤

λ(1 + ǫ)
l2 (p)
λ−ǫ

This shows that we can approximate the longest path problem to within a constant factor of λ(1+ǫ)
λ−ǫ , a contradiction.
Therefore, the minimum cost-to-time ratio simple path problem cannot be approximated to within any constant factor
unless P = N P .

General Objective Function
For general objective functions, the following hardness results were proven by Nikolova, Brand, and Karger (2006):
Fact 1. Suppose function g attains a global minimum at y >
0. Then problem (1) of finding an optimal s − t simple path
is NP-hard.
Fact 2. Consider problem (1) of finding an optimal s − t
simple path with f being a rank-1 function. Let p∗ be the
optimal path, and l∗ = l(p∗ ). If g is any strictly decreasing
and positive function with slope of absolute value at least
λ > 0 on [0, l∗ ], then there does not exist a polynomialtime constant factor approximation algorithm for finding an
optimal simple path, unless P = N P .
Although these facts are proven for rank-1 functions, they
show that for a large class of objective functions, the problem of finding the optimal simple path is not only NP-hard,
but also NP-hard to approximate within any constant factor.
As a result, we turn our attention to the problem that
accepts non-simple paths. While this problem is also NPhard (Nikolova, Brand, and Karger 2006), we are able to design a polynomial-time algorithm to approximate the optimal solution arbitrarily well.

Approximation Algorithms
Consider problem (1) that accepts non-simple paths. For
some cases, it is possible that there does not exist an optimal path of finite length. Consider an example of a rank 1
monotonic decreasing function g(x) = 1/x. Suppose there
is a positive weight loop in any of the s − t paths. Then,
we can always find a better solution by visiting such a loop
arbitrarily many times: the optimal path here is ill-defined.
Naturally, for the problem that accepts non-simple paths,
the path polytope is infinite. Even when the optimal path is
finite, for a large class of problems, including the minimum
cost-to-time ratio path problem, finding a finite subset of the
path polytope that contains the optimal path is difficult, as
shown in our Hardness section above. In this section, we
will show that, under some additional constraints, this problem becomes well-defined and well-approximable. In what
follows, we identify the additional constraints and present
the algorithms to solve the corresponding problems.

Hop Constraint
Suppose the path contains at most γ hops, then the set of
feasible paths Pt becomes finite and the problem is welldefined. Denote hop(p) to be the number of hops in path p,
or equivalently, the number of edges in p. Note that an edge
can be counted multiple times if path p contains loops.
To approximate the optimal path, we approximate the path
polytope with polynomially many paths, and then search for
the best one among them. To approximate the path polytope, we first identify a region of weights space W that contains all paths starting from s, which are within γ edges.
We can upper- and lower-bound this region as follows: For
each criterion k = 1, . . . , d, define cmin
= mine∈E we,k
k
= maxe∈E we,k . Then for any path p that starts
and cmax
k
from the source s and contains at most γ edges, we have
max
lk (p) ∈ [cmin
], for each criterion k ∈ {1, . . . , d}.
k , γck
Q
max
Next, we partition the region dk=1 [cmin
] of the
k , γck
weights space W into polynomially many hypercubes.
Specifically, for each criterion k ∈ {1, 2, . . . , d}, let ǫ >
0 be a given desired approximation factor, and Ck =
cmax
/cmin
k
k . Define Γk = {0, 1, . . . , ⌊log(1+ǫ) (γCk )⌋} as the
max
]
set of points that evenly partitions the segment [cmin
k , γck
on the log scale. Then, we generate a d-dimensional lattice
Γ = Γ1 ×Γ2 ×· · ·×Γd according to these sets. After that, we
define a hash function h = (h1 , h2 , . . . , hd ) : P → Γ that
maps a path to a point on the lattice Γ. Each hk : P → Γk is
(p)
defined as hk (p) = ⌊log(1+ǫ) lckmin
⌋.
k
The main part of the algorithm iterates over i ∈
{1, 2, . . . , γ}, sequentially constructing s − v sub-paths containing at most i edges, for each vertex v ∈ V . For each
iteration i and each vertex v ∈ V , we maintain at most
|Γ| configurations as a d-dimensional table Πiv , indexed by
y ∈ Γ. Each configuration Πiv (y) can be either an s − v
path p of at most i edges and h(p) = y, given there is one,
or null otherwise. The table can be implemented in various
ways. 2 Here we assume that given index y ∈ Γ, both check2
In practice, we can either allocate the memory of the entire
table in the beginning, or use another data structure that only stores

ing whether the configuration Πiv (y) is null, retrieving the
path in Πiv (y), and inserting/updating a path in Πiv (y) can
be done in TΠ = TΠ (n, |Γ|) time.
At iteration i, for each vertex u, we will construct a set
of s − u sub-paths containing i edges based on (i − 1)-edge
sub-paths we previously constructed. We loop over each vertex v ∈ V and each edge e = (v, u) incident to v, and we
append the edge to the end of each (i − 1)-edge s − v path in
Πi−1
v . However, not all generated sub-paths will be stored.
Consider any s − u path p generated with this procedure, it
will be stored in table Πiu only if Πiu (h(p)) is empty. With
this technique, we can ensure that the number of sub-paths
we record in each iteration is at most polynomial, because it
is bounded by the size of the lattice Γ times the number of
vertices. This procedure is outlined in Algorithm 1.
Algorithm 1 Nonlinear Objective Shortest Path with Hopconstraint
1: for each y ∈ Γ, v ∈ V , and i = 1, 2, . . . , γ do
2:
Set Πiv (y) = null
3: Set Π0s = {s}.
4: for i = 1 to γ do
5:
Set Πiv = Πi−1
for each vertex v ∈ V .
v
6:
for each vertex v ∈ V do
7:
for each path p ∈ Πi−1
with i − 1 edges do
v
8:
for each edge e = (v, u) ∈ E do
9:
Set p′ be the path that appends edge e to the
tail of p.
10:
Compute hash y = h(p′ ).
11:
if Πiu (y) = null then
12:
Πiu (y) = p′ .
13: return maxp∈Πγt f (p)
To prove the correctness of this algorithm, we show the
following lemmas:
Lemma 1. Let pu and p′u be two s − u paths such that for
each criterion k ∈ {1, 2, . . . , d},
| log lk (pu ) − log lk (p′u )| ≤ log(1 + ǫ).

(4)

Suppose there is a vertex v and an edge e such that e =
(u, v) ∈ E. Let pv and p′v be the s − v paths that append
(u, v) to the tails of pu and p′u , respectively. Then, for each
criterion k ∈ {1, 2, . . . , d},
| log lk (pv ) − log lk (p′v )| ≤ log(1 + ǫ)
Proof. By (4), it directly follows that
lk (pv ) = lk (pu ) + lk (e) ≤ (1 + ǫ)lk (p′u ) + lk (e)

≤ (1 + ǫ)(lk (p′u ) + lk (e)) = (1 + ǫ)lk (p′v )

lk (p′v ) = lk (p′u ) + lk (e) ≤ (1 + ǫ)lk (pu ) + lk (e)
≤ (1 + ǫ)(lk (pu ) + lk (e)) = (1 + ǫ)lk (pv )
Combining the above two inequalities yields the proof.

the used entries of the table. According to our experimental results,
only a small portion of the table Πiv will be used.

Lemma 2. For any v ∈ V , and for any path s − v that is of
at most i edges, there exists an s − v path p′ ∈ Πiv such that
for each criterion k ∈ {1, 2, . . . , d},
| log lk (p) − log lk (p′ )| ≤ i log(1 + ǫ)

Proof. We prove this lemma by induction on the number of
edges in a path. The base case is a direct result from the definition of the hash function h. For the induction step, consider vertex v ∈ V , and we would like to prove the statement
is correct for any s − v sub-paths of at most i∗ edges, given
the statement is true for any i < i∗ and any vertices. Let pv
be any s − v path no more than i∗ edges. If pv is of i′ < i∗
edges, then by the induction hypothesis, there exists an s − v
′
path p′v in Πiv such that | log(lk (pv )/lk (p′v ))| ≤ i′ log(1+ǫ).
∗
The lemma is proved for this case since p′v is in Πiv as well.
Next consider pv to be an s − v path with i∗ edges, and suppose pv is formed by appending the edge (u, v) to an s − u
path pu . By the induction hypothesis, we can see that there
∗
is an s − u path p′u ∈ Πiu −1 such that for each criterion
k ∈ {1, 2, . . . , d},
| log lk (pu ) − log lk (p′u )| ≤ (i∗ − 1) log(1 + ǫ)

Then, with Lemma 1, as we form s − v sub-paths pv and
p′v by appending (u, v) to the end of pu and p′u respectively,
we have the following relationship for each criterion k ∈
{1, 2, . . . , d}:
| log lk (pv ) − log lk (p′v )| ≤ (i∗ − 1) log(1 + ǫ)
p′′v

h(p′′v )

(5)

h(p′v ).

Consider any s − v path
such that
=
We
must have | log lk (p′v ) − log lk (p′′v )| ≤ log(1 + ǫ) for each
criterion k ∈ {1, . . . , d}, according to the definition of the
hash function h. Combining this with (5), we can see that
∗
even for the case that path p′v is not stored in the table Πiv ,
∗
the path p′′v = Πiv (h(p′v )) must satisfy
| log lk (pv ) − log lk (p′′v )| ≤ i∗ log(1 + ǫ)
for each criterion k ∈ {1, . . . , d}. This indicates that for any
∗
s − v path pv within i∗ edges, there exists a path p′′v in Πiv
∗
such that their ratio is bounded by (1 + ǫ)i . Q.E.D.
Now, we are ready to state and prove the main result:
Theorem 2. Suppose g defined in (2) is β-Lipschitz on
the log-log scale. Then Algorithm 1 is a (1 + ǫ)βdγ approximation algorithm for the γ-hop-constrained nonlinear objective shortest path problem. Besides, Algorithm 1
log(γC) d
has time complexity O(γm( log(1+ǫ)
) TΠ ), where C =
maxk∈{1,2,...,d} Ck .
Proof. By Lemma 2, we can see that for any s − t path p of
at most γ edges, there exists an s − t path p′ ∈ Πγt such that
| log lk (p) − log lk (p′ )| ≤ γ log(1 + ǫ),

∀k = 1, 2, . . . , d

It then follows from (3) that our algorithm finds a path p′
such that | log f (p′ ) − log f (p∗ )| ≤ βdγ log(1 + ǫ). Then,
we have
f (p′ ) ≤ (1 + ǫ)βdγ f (p∗ )
This shows that p′ is an (1 + ǫ)βdγ -approximation to p∗ .

Next, we show the time complexity. It is easy to see that
at each iteration, the algorithm generates at most m|Γ| subpaths. Each sub-path requires at most O(TΠ ) time to operlog(γC) d
ate. Since |Γ| = ( log(1+ǫ)
) , we can conclude that Algolog(γC) d
) TΠ ).
rithm 1 runs in time O(γm( log(1+ǫ)

Note that we can obtain a (1+δ)-approximation algorithm
by setting δ = (1 + ǫ)βdγ − 1. With this setting, then Algo)d TΠ ). If we
rithm 1 has time complexity O(γm( βdγ log(γC)
δ
assume γ = O(n), then Algorithm 1 is indeed an FPTAS.

Linear Constraint
The hop constraint we considered can be relaxed: we now
consider the more general problem that anyP
returned path p
must satisfy an additional linear constraint e∈p we,d+1 ≤
b, for some budget b > 0 and some weight vector wd+1 ∈
Rm
entries. We define the (d + 1)-th
++ with strictly positive
P
criterion ld+1 (p) = e∈p we,d+1 , which can be interpreted
as having a budget b for a path. To solve this problem, we can
find an upper bound of the number of edges for any feasible
s − t path. A simple upper bound can be given by
b − P ∗ w

e∈pd+1 e,d+1
γ=
(6)
+ hopmin
mine∈E we,d+1
P
where p∗d+1 = arg minp∈P e∈p we,d+1 is the shortest path
with respect to the weight wd+1 , and hopmin is the minimum number of edges for any s − t path. Note that either
hopmin and p∗d+1 can be solved by Dijkstra’s or BellmanFord’s shortest path algorithms efficiently.
Then, we can adapt the techniques discussed for the hopconstrained problem but with some modifications. Instead of
assigning the least hop path to a configuration, we now assign the path with the least (d+ 1)-th criterion. Formally, the
modification is to change line 11 and line 12 of Algorithm 1
to : Assign p′ to Πiu (y) if p′ satisfies both of the following:
• ld+1 (p′ ) < b

• Πiu (y) is null or ld+1 (p′ ) < ld+1 (Πiu (y))

As a corollary of Theorem 2, we have the following result:

Corollary 1. Algorithm 1 with the modifications stated
above is a (1 + ǫ)βdγ -approximation algorithm for the
linear-constrained nonlinear objective shortest path problem, where γ is defined as in Eq. (6).

Application: Deadline Problem
With the techniques mentioned in the above section, we are
able to solve various problems, including the minimum costto-time ratio path problem with either a hop or a linear budget constraint. In this section, we discuss a related problem,
which is the deadline problem in a stochastic setting.
The deadline problem is to find a path that is the most
likely to be on time, which is defined as follows: Suppose
each edge is associated with an independent random variable Xe , which we call the travel time of edge e. Given
a deadline D > 0, we are going to find an s − t path
such that the probability of being on time is maximized:

Table 1: Deadline Problem with Hop Constraint
Network

Hops

5 × 5 Grid
10 × 10 Grid
Anaheim

12
12
15
15
15

Worst-case
Theoretical
Accuracy (α)
(Exhaustive)
2.2923
2.2926
2.2891
3.0436

Memory
Usage
(106 paths)
1.63
0.67
4.30
18.05
9.60

Run
time (s)
3.441
2.057
20.276
83.430
37.671

P
maxp∈Pt Pr( e∈p Xe < D). We assume that the random
variables {Xe } are Gaussian. Based on this, we denote the
mean travel time for edge e as µe and variance as σe2 . For
simplicity, we assume for each edge e ∈ E, its mean µe
and variance σe2 are bounded by µe ∈ [µmin , µmax ], and
2
2
σe2 ∈ [σmin
, σmax
]. The problem can hence be written as:
P


D − e∈p µe
q
(7)
max Φ
P
p∈Pt
2
e∈p σe

where Φ(·) is the cumulative distribution function for
the standard normal distribution. The objective function
in (7) is a rank 2 function. This problem is studied in
(Nikolova et al. 2006) for a risk-averse shortest path problem, where they considered the case that the optimal path
has mean travel time less than the deadline: for this case (7)
is a monotonic decreasing function. In this paper, we consider the case that all feasible s − t paths have mean travel
time strictly greater than the deadline. This means that we
assume each path has poor performance. Then, the objective function in (7) becomes monotonic decreasing with respect to the mean but monotonic increasing with respect to
the variance, for which known algorithms no longer apply.
However, we are able to use techniques presented in this paper to solve this problem under either a hop or an additional
linear constraint.

Theorem 3. Suppose
P each 2s − t path p ∈ Pt satisfies
P
e∈p σe > S. For the deadline probe∈p µe > D and
lem with a hop constraint γ, if Algorithm 1 returns some
path p′ such that f (p′ ) > Φ(−3) ≈ 0.0013, then p′ is
an α-approximation for the deadline problem, where α =
6.568(3+ √D )γ
S
min{384.62, (1 + ǫ)
)}. Similarly, if p′ is such
′
that f (p ) > Φ(−2) ≈ 0.023, then α = min{21.93, (1 +
4.745(2+ √DS )γ
ǫ)
}.

Note that this theorem does not guarantee Algorithm 1
admits FPTAS for the deadline problem, since
√ given α, the
running time is polynomial in the factor D/ S.

Experimental Evaluations
We tested our algorithm on a grid graph and a real transportation network. The algorithm is implemented in C++.
Experiments are run on an Intel Core i7 1.7 GHz (I7-4650U)
processor. Due to memory constraints, the table {Πiv |v ∈ V }
is implemented as a binary search tree, where query, insertion, and update operations can be done in time TΠ =

Figure 2: Memory usage for running our algorithm on a 5×5
grid graph to the number of iterations.
O(log(n|Γ|)). Memory turns out to be the limiting factor for
the problem size and accuracy available to our experiments.
In this section, memory usage refers to the total number of
sub-paths maintained in the table {Πiv |v ∈ V }.
We tested the deadline problem with a hop constraint on
a 5 × 5 grid graph, 10 × 10 grid graph, and the Anaheim
network (416 vertices, 914 edges) from the real world data
set (Bar-Gera 2002). The grid graphs are bi-directional, and
the mean and the variance for each edge are randomly generated from [0.1, 5]. We routed from node (0, 0) to node (4, 4)
on the 5 × 5 grid, and from (1, 1) to (8, 8) on the 10 × 10
grid. The Anaheim dataset provides the mean travel time.
The variance for each edge is randomly generated from 0 to
the mean. The source and destination are randomly chosen.
Table 1 summarizes the results on the datasets, which are
the average of 20 experiments. Even though theoretically the
algorithm can be designed for arbitrary desired accuracy, it is
limited by the memory of the environment.3 However, comparing with exhaustive search, we found that the practical
accuracy is 100% on 5 × 5 grid graphs.4 This means that
our algorithm is far more accurate than its theoretical worst
case bound. We explain this phenomenon through Figure 2,
which shows the number of sub-paths generated up to each
iteration. We see that the number of sub-paths generated in
the initial iterations grows exponentially, just as in exhaustive search, but levels off eventually. Recall Lemma 2, which
tells us that an error is induced when a sub-path is eliminated
due to similarity to a saved sub-path, and Figure 2 suggests
that this rarely happens in the initial iterations.

Conclusion
We investigated the shortest path problem with a general
nonlinear and non-monotonic objective function. We proved
3

It takes about 3GB physical memory usage for the 18M paths
in the 10 × 10 grid network.
4
Exhaustive search becomes prohibitive for paths with more
than 12 hops on 5 × 5 grid graphs.

that this problem is hard to approximate for simple paths and
consequently, we designed and analyzed a fully polynomial
approximation scheme for finding the approximately optimal non-simple path under either a hop constraint or an additional linear constraint. We showed that this algorithm can
be applied to the cost-to-time ratio problem and the deadline problem. Our experiments show that our algorithm is
capable of finding good approximations efficiently.

Acknowledgement
This work was supported in part by NSF grant numbers
CCF-1216103, CCF-1350823, CCF-1331863, and a Google
Faculty Research Award.

[Nikolova, Brand, and Karger 2006] Nikolova, E.; Brand,
M.; and Karger, D. R. 2006. Optimal route planning under uncertainty. In ICAPS, volume 6, 131–141.
[Nikolova 2010] Nikolova, E. 2010. Approximation algorithms for offline risk-averse combinatorial optimization.
[Papadimitriou and Yannakakis 2000] Papadimitriou, C. H.,
and Yannakakis, M. 2000. On the approximability of tradeoffs and optimal access of web sources. In Foundations of
Computer Science, 2000. Proceedings. 41st Annual Symposium on, 86–92. IEEE.
[Tsaggouris and Zaroliagis 2009] Tsaggouris, G., and Zaroliagis, C. 2009. Multiobjective optimization: Improved fptas for shortest paths and non-linear objectives with applications. Theory of Computing Systems 45(1):162–186.

References
[Ahuja, Batra, and Gupta 1983] Ahuja, R.; Batra, J.; and
Gupta, S. 1983. Combinatorial optimization with rational
objective functions: A communication. Mathematics of Operations Research 8(2):314–314.
[Bar-Gera 2002] Bar-Gera, H. 2002. Transportation network
test problems.
[Correa, Fernandes, and Wakabayashi 2010] Correa, J.; Fernandes, C. G.; and Wakabayashi, Y. 2010. Approximating a class of combinatorial problems with rational objective
function. Mathematical programming 124(1-2):255–269.
[Goyal and Ravi 2013] Goyal, V., and Ravi, R. 2013. An
fptas for minimizing a class of low-rank quasi-concave
functions over a convex set. Operations Research Letters
41(2):191–196.
[Guérin and Orda 1999] Guérin, R. A., and Orda, A. 1999.
Qos routing in networks with inaccurate information: theory and algorithms. IEEE/ACM Transactions on Networking
(TON) 7(3):350–364.
[Horst, Pardalos, and Van Thoai 2000] Horst, R.; Pardalos,
P. M.; and Van Thoai, N. 2000. Introduction to global optimization. Springer Science & Business Media.
[Karger, Motwani, and Ramkumar 1997] Karger, D.; Motwani, R.; and Ramkumar, G. 1997. On approximating the
longest path in a graph. Algorithmica 18(1):82–98.
[Kelner and Nikolova 2007] Kelner, J. A., and Nikolova, E.
2007. On the hardness and smoothed complexity of quasiconcave minimization. In Foundations of Computer Science,
2007. FOCS’07. 48th Annual IEEE Symposium on, 472–
482. IEEE.
[Megiddo 1979] Megiddo, N. 1979. Combinatorial optimization with rational objective functions. Mathematics of
Operations Research 4(4):414–424.
[Mittal and Schulz 2013] Mittal, S., and Schulz, A. S. 2013.
An fptas for optimizing a class of low-rank functions over a
polytope. Mathematical Programming 141(1-2):103–120.
[Nikolova et al. 2006] Nikolova, E.; Kelner, J. A.; Brand, M.;
and Mitzenmacher, M. 2006. Stochastic shortest paths via
quasi-convex maximization. In Algorithms–ESA 2006, 552–
563. Springer.

Appendix: Missing Proofs
Proof of Corollary 1
We need the following modified version of Lemma 2 to
prove Corollary 1:
Lemma 3. For any v ∈ V , and for any path s − v that is of
at most i edges, there exists an s − v path p′ ∈ Πiv such that
1
lk (p)
≤
≤ (1 + ǫ)i ,
i
(1 + ǫ)
lk (p′ )
and

∀k = 1, 2, . . . , d

ld+1 (p′ ) ≤ ld+1 (p)

Proof. We prove this lemma by induction on the number
of edges in a path as what we have done in Lemma 2. The
base case is a direct result from the definition of the hash
function h. For the induction step, consider vertex v ∈ V ,
and we would like to prove the statement is correct for any
s − v sub-paths of at most i∗ edges, given the statement is
true for any i < i∗ and any vertices.
Let pv be any s − v path of no more than i∗ edges. First
consider the case that the path pv is of i′ < i∗ edges, then
′
by induction hypothesis, there exists an s − v path p′v in Πiv
′
such that |lk (pv )/lk (p′v )| ≤ (1+ǫ)i . Then consider the s−v
∗
path p′′v ∈ Πiv such that h(p′′v ) = h(p′v ). By the definition
of the hash function h, it must hold that
1
lk (p′v )
≤
≤ 1 + ǫ,
1+ǫ
lk (p′′v )

∀k = 1, 2, . . . , d

Then we have
′
1
lk (pv )
≤
≤ (1 + ǫ)i +1 ,
(1 + ǫ)i′ +1
lk (p′′v )

∀k = 1, 2, . . . , d

By the induction hypothesis and the replacement rule in
the algorithm, we have ld+1 (p′′v ) ≤ ld+1 (p′v ) ≤ ld+1 (pv ).
Therefore the lemma is proved for this case.
Next consider the case that pv is s − v path with i∗ edges,
and suppose pv is formed by appending the edge (u, v) to an
s − u path pu . By the induction hypothesis, we can see that
∗
there is an s − u path p′u ∈ Πiu −1 such that
∗
lk (pu )
1
≤ (1 + ǫ)i −1 ,
∗ −1 ≤
i
′
(1 + ǫ)
lk (pu )

∀k = 1, 2, . . . , d

and ld+1 (p′u ) ≤ ld+1 (pu ). Then, with Lemma 1, as we form
the s − v sub-paths pv and p′v by appending (u, v) to the end
of pu and p′u respectively, we have the following relationship:
∗
1
lk (pv )
≤
≤ (1 + ǫ)i −1 ,
(1 + ǫ)i∗ −1
lk (p′v )

∀k = 1, 2, . . . , d

(8)
Consider any s − v path p′′v such that h(p′′v ) = h(p′v ). The
following is always satisfied according to the definition of
the hash function h:
1
lk (p′v )
≤
≤ 1 + ǫ,
1+ǫ
lk (p′′v )

∀k = 1, 2, . . . , d

Combining this with (8), we can see that the path p′′v =
∗
Πiv (h(p′v )) must satisfy
∗
lk (pv )
1
≤ (1 + ǫ)i ,
∗ ≤
i
′′
(1 + ǫ)
lk (pv )

∀k = 1, 2, . . . , d

and ld+1 (p′′v ) ≤ ld+1 (pv ). This indicates that for any s − v
∗
path pv which is within i∗ edges, there exists a path p′′v in Πiv
∗
such that their ratio is bounded by (1 + ǫ)i , and p′′v always
has the smaller (d + 1)-th weight than pv . Q.E.D.
With this lemma, we are able to prove Corollary 1:
Proof of Corollary 1. By Lemma 3, we can see that for any
s − t path p that is within γ edges, there exists an s − t path
p′ ∈ Πγt such that
log

lk (p)
≤ γ log(1 + ǫ) ∀k = 1, 2, . . . , d
lk (p′ )

and ld+1 (p′ ) ≤ ld+1 (p). It then follows from (3) that our
algorithm finds a path p′ such that
log

f (p′ )
≤ βdγ log(1 + ǫ)
f (p∗ )

Then, we have
f (p′ ) ≤ (1 + ǫ)βdγ f (p∗ )

Clearly p′ satisfies the constraint ld+1 (p′ ) ≤ b since
ld+1 (p′ ) ≤ ld+1 (p∗ ) ≤ b. This shows that p′ is an (1+ǫ)βdγ approximation to p∗ .

Proof of Theorem 3
Before we prove Theorem 3, we need the following lemma:
D
√ ) is 3.284(3 + √
)Lemma 4. The function Φ( D−x
y
S
Lipschitz on log-log scale with respect to L1√norm on the
region C = {(x, y)|x > D, y > S, x − D ≤ 3 y}.
Proof. We want to show that for any (u1√
, v1 ), (u2 , v2 ) ∈
′
u
v
u
C = {(u, v)|e > D, e > S, e − D ≤ 3 ev },




D − eu2
D − eu1
√
√
− log Φ
log Φ
ev1
ev2


D
(|u1 − u2 | + |v1 − v2 |) (9)
≤ 3.284 3 + √
S

u

√
We take the derivatives from the function log Φ( D−e
):
ev


u
√


Φ′ D−e
v
u
u
e
D−e
∂
e

log Φ √ v
= √ v · 
∂u
u
e
e
D−e
√
Φ
ev

 u
D
e −D
(10)
≤ 3.284 √ v + √ v
e
e


D
≤ 3.284 3 + √ v
(11)
e


D
(12)
≤ 3.284 3 + √
S


u
′ D−e
√


Φ
ev
∂
D − eu
D − eu

log Φ √ v
= ev · √ 3 · 
∂v
u
e
2 ev
√
Φ D−e
ev

3
× 3.284
(13)
2
where Inequality (10) comes from the fact that
Φ′ (x)/Φ(x) ≤ 3.284 for x ∈ [−3, 0), Inequality
(11)
√
u
v . Since
comes from
the
fact
that
e
−
D
<
3
e
u
√
log Φ( D−e
) is differentiable in C ′ , we obtain (9).
ev
≤

Proof of Theorem 3. Let l1 (p) denote the mean traveling
time for path p, and l2 (p) denote the variance for path p.
Further denote l(p) = (l1 (p), l2 (p)). By Lemma 2, we can
see that for the optimal s − t path p∗ , there exists an s − t
path p′′ ∈ Πγt such that
log

lk (p∗ )
≤ γ log(1 + ǫ)
lk (p′′ )

Denote the region C = {(x, y)|x > D, y > S, x − D ≤
√
√ ) ∈
3 y}. We can see that (x, y) ∈ C if and only if Φ( D−x
y
[Φ(−3), 0.5) and y > S. The optimal path must satisfy
l(p∗ ) ∈ C since f (p∗ ) ≥ f (p′ ) > Φ(−3).
First consider the case that l(p′′ ) is in the region C. Then
we can adapt the same technique as in the proof of Theorem 2 and the smoothness condition we showed in Lemma 4
to claim that the path p′ returned by the algorithm satisfies
2×3.284×(3+ √DS )γ

f (p′′ )

2×3.284×(3+ √DS

f (p′ )

f (p∗ ) ≤ (1 + ǫ)

≤ (1 + ǫ)

)γ

Now consider the case that l(p′′ ) is not in the region C,
then there must
√ exist a point (x0 , y0 ) ∈ C on the line L =
{x − D = 3 y} such that
x0
≤ γ log(1 + ǫ)
l1 (p∗ )
y0
≤ γ log(1 + ǫ)
log
l2 (p∗ )

log

It then follows from Lemma 4 that


√ 0)
Φ( D−x
D
y0
γ log(1 + ǫ)
≤ 2 × 3.284 × 3 + √
log
f (p∗ )
S

Since the algorithm returns some other path p′ such that
√ 0 ), we must have
f (p′ ) > Φ(−3) = Φ( D−x
y0
6.568(3+ √DS )γ

Φ(−3)

6.568(3+ √DS )γ

f (p′ )

f (p∗ ) ≤ (1 + ǫ)

< (1 + ǫ)

However, the approximation ratio is upper-bounded by
0.5/Φ(−3) ≈ 384.62, so this shows that p′ is an
6.568(3+ √DS )γ
}-approximation to p∗ . We
min{384.62, (1 + ǫ)
can apply the same technique for the case that f (p′ ) >
Φ(−2) or any other values.

