TY - GEN

T1 - Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs

AU - Bernstein, Aaron

PY - 2012

Y1 - 2012

N2 - We present a significantly faster algorithm for the restricted shortest path problem, in which we are given two vertices s, t, and the goal is to find the shortest path that is subject to a side constraint. More formally, rather than just having a single weight, each edge has two weights: a cost-weight, and a delay-weight. We are given a threshold T which corresponds to the maximum delay we can afford, and the goal is to find the s - t path that minimizes total cost while still having delay-length at most T. There are many applications for this problem, as it can model situations where we need a path that has to achieve some balanced trade off between two different parameters. The exact version of the problem is known to be NP-hard [3], but there has been a series of results on (1 + ε) approximations, which culminated in a Õ(mn) algorithm for general graphs in 1999 [4, 8]. We present the first result to break though this barrier, achieving a close to linear running time - technically it is Õ(m(2/ε) O(√log(n)loglog(n))). It does have several drawbacks, however. It is randomized (Las Vegas), it only works for undirected graphs, and it approximates both parameters (previous algorithms found a (1 + ε) shortest path with delay exactly T or less, or a shortest path with delay at most (1 + ε)T, whereas our algorithm incurs a (1+ε) approximation on both counts.) Our result presents an entirely new approach to the problem, which could potentially be generalized to work for directed graphs and to approximate only one of the parameters.

AB - We present a significantly faster algorithm for the restricted shortest path problem, in which we are given two vertices s, t, and the goal is to find the shortest path that is subject to a side constraint. More formally, rather than just having a single weight, each edge has two weights: a cost-weight, and a delay-weight. We are given a threshold T which corresponds to the maximum delay we can afford, and the goal is to find the s - t path that minimizes total cost while still having delay-length at most T. There are many applications for this problem, as it can model situations where we need a path that has to achieve some balanced trade off between two different parameters. The exact version of the problem is known to be NP-hard [3], but there has been a series of results on (1 + ε) approximations, which culminated in a Õ(mn) algorithm for general graphs in 1999 [4, 8]. We present the first result to break though this barrier, achieving a close to linear running time - technically it is Õ(m(2/ε) O(√log(n)loglog(n))). It does have several drawbacks, however. It is randomized (Las Vegas), it only works for undirected graphs, and it approximates both parameters (previous algorithms found a (1 + ε) shortest path with delay exactly T or less, or a shortest path with delay at most (1 + ε)T, whereas our algorithm incurs a (1+ε) approximation on both counts.) Our result presents an entirely new approach to the problem, which could potentially be generalized to work for directed graphs and to approximate only one of the parameters.

UR - http://www.scopus.com/inward/record.url?scp=84860128893&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860128893&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84860128893

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 189

EP - 201

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -