Current browse context:
cs.DS
Change to browse by:
References & Citations
Computer Science > Data Structures and Algorithms
Title: A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates
(Submitted on 22 Aug 2022 (this version), latest version 1 Aug 2023 (v4))
Abstract: The shortest path problem in graphs is a cornerstone for both theory and applications. Existing work accounts for edge weight access time, but generally ignores edge weight computation time. In this paper we present a generalized framework for weighted directed graphs, where each edge cost can be dynamically estimated by multiple estimators, that offer different cost bounds and run-times. This raises several generalized shortest path problems, that optimize different aspects of path cost while requiring guarantees on cost uncertainty, providing a better basis for modeling realistic problems. We present complete, anytime algorithms for solving these problems, and provide guarantees on the solution quality.
Submission history
From: Eyal Weiss [view email][v1] Mon, 22 Aug 2022 22:07:27 GMT (30kb)
[v2] Wed, 25 Jan 2023 11:23:53 GMT (33kb)
[v3] Mon, 13 Mar 2023 12:17:56 GMT (62kb,D)
[v4] Tue, 1 Aug 2023 13:42:17 GMT (88kb,D)
Link back to: arXiv, form interface, contact.