Current browse context:
cs.DS
Change to browse by:
References & Citations
Computer Science > Data Structures and Algorithms
Title: Tightest Admissible Shortest Path
(Submitted on 15 Aug 2023 (v1), last revised 27 Mar 2024 (this version, v2))
Abstract: The shortest path problem in graphs is fundamental to AI. Nearly all variants of the problem and relevant algorithms that solve them ignore edge-weight computation time and its common relation to weight uncertainty. This implies that taking these factors into consideration can potentially lead to a performance boost in relevant applications. Recently, a generalized framework for weighted directed graphs was suggested, where edge-weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. We build on this framework to introduce the problem of finding the tightest admissible shortest path (TASP); a path with the tightest suboptimality bound on the optimal cost. This is a generalization of the shortest path problem to bounded uncertainty, where edge-weight uncertainty can be traded for computational cost. We present a complete algorithm for solving TASP, with guarantees on solution quality. Empirical evaluation supports the effectiveness of this approach.
Submission history
From: Eyal Weiss [view email][v1] Tue, 15 Aug 2023 14:39:05 GMT (84kb,D)
[v2] Wed, 27 Mar 2024 21:46:41 GMT (175kb,D)
Link back to: arXiv, form interface, contact.