Gal A. Kaminka: Publications

Sorted by DateClassified by Publication TypeClassified by TopicGrouped by Student (current)Grouped by Former Students

A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates

Eyal Weiss, Ariel Felner, and Gal A. Kaminka. A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates. In Proceedings of the European Conference on Artificial Intelligence (ECAI), pp. 2607–2614, 2023.
An earlier version was published at the RDDPS workshop at ICAPS 2023 conference.

Download

[PDF]328.7kB  

Abstract

The shortest path problem in graphs is a cornerstone of AI theory and applications. Existing algorithms generally ignore edge weight computation time. We present a generalized framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. This raises several generalized variants of the shortest path problem. We introduce the problem of finding a path with the tightest lower-bound on the optimal cost. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.

Additional Information

BibTeX

@inproceedings{ecai23,
 author = {Eyal Weiss and Ariel Felner and Gal A. Kaminka},
 title = {A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates},
 booktitle = ECAI, 
 year = {2023},
 pages= {2607--2614},
  wwwnote = {An earlier version was published at the RDDPS workshop at ICAPS 2023 conference.},
  abstract = {  The shortest path problem in graphs is a cornerstone of AI theory and applications. 
   Existing algorithms generally ignore edge weight computation time. 
   We present a generalized framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. 
   This raises several generalized variants of the shortest path problem.
   We introduce the problem of finding a path with the tightest lower-bound on the optimal cost. 
   We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.
  },
}

Generated by bib2html.pl (written by Patrick Riley ) on Thu Feb 22, 2024 11:36:58