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 -