Silos and Lazy Shortest Paths on Ordered Directed Acyclic Graphs
Published:
Many dynamic programs can be interpreted as shortest path problems on ordered directed acyclic graphs (DAGs), where edge weights are optimal values of non-trivial optimization problems. In such cases using approximate lower-bounding weights can reduce computational cost. In this paper we introduce general formalisms to study these lazy shortest path problems where edge weight computation is delayed or avoided. Our primary contribution in this area is introducing the concept of a graph Silo, which captures the degree to which a graph permits paths that are nearly tied to the shortest path. We show that such formalisms are especially useful in bounding behavior of canonical lazy shortest path algorithms such as LazySP. We then use our formalisms to motivate the introduction of a new class of lazy shortest path algorithms that introduce lazy label correcting algorithms to the lazy shortest path literature. Empirically we find that on graphs with many near ties our proposed Pruning Shortest Path family of algorithms outperforms the LazySP framework.