Shortest Path Discovery Problems: A Framework, Algorithms and Experimental Results

Shortest Path Discovery Problems: A Framework, Algorithms and Experimental Results. Szepesvári, C. In AAAI, pages 550–555, 2004.

Paper abstract bibtex

In this paper we introduce and study Shortest Path Discovery (SPD) problems, a generalization of shortest path problems: In SPD one is given a directed edge-weighted graph and the task is to find a the shortest path for fixed source and target nodes such that initially the edge-weights are unknown, but they can be queried. Querying the cost of an edge is expensive and hence the goal is to minimize the total number of edge cost queries executed. In this article we characterize some common properties of sound SPD algorithms, propose a particular algorithm that is shown to be sound and effective. Experimental results on real-world OCR task demonstrate the usefulness of the approach whereas the proposed algorithm is shown to yield a substantial speed-up of the recognition process.

@inproceedings{Szepesvari2004a,
	abstract = {In this paper we introduce and study Shortest Path Discovery (SPD) problems, a generalization of shortest path problems: In SPD one is given a directed edge-weighted graph and the task is to find a the shortest path for fixed source and target nodes such that initially the edge-weights are unknown, but they can be queried. Querying the cost of an edge is expensive and hence the goal is to minimize the total number of edge cost queries executed. In this article we characterize some common properties of sound SPD algorithms, propose a particular algorithm that is shown to be sound and effective. Experimental results on real-world OCR task demonstrate the usefulness of the approach whereas the proposed algorithm is shown to yield a substantial speed-up of the recognition process.},
	author = {Szepesv{\'a}ri, Cs.},
	booktitle = {AAAI},
	keywords = {online learning, theory, search, application, image processing, shortest path problem},
	pages = {550--555},
	title = {Shortest Path Discovery Problems: A Framework, Algorithms and Experimental Results},
	url_paper = {szepes-aaai2004.pdf},
	year = {2004}}

Downloads: 0