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

Aaron Bernstein

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
    Pages189-201
    Number of pages13
    StatePublished - 2012
    Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
    Duration: Jan 17 2012Jan 19 2012

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

    Other

    Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
    Country/TerritoryJapan
    CityKyoto
    Period1/17/121/19/12

    ASJC Scopus subject areas

    • Software
    • General Mathematics

    Fingerprint

    Dive into the research topics of 'Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs'. Together they form a unique fingerprint.

    Cite this