Dasgupta, Pallab ; Chakrabarti, P. P. ; DeSarkar, S. C.
(1995)
*A near optimal algorithm for the extended cow-path problem in the presence of relative errors*
In: 15th Conference on Foundations of Software Technology and Theoretical Computer Science, 18–20 December 1995, Bangalore, India.

Full text not available from this repository.

Official URL: http://link.springer.com/chapter/10.1007%2F3-540-6...

Related URL: http://dx.doi.org/10.1007/3-540-60692-0_38

## Abstract

In classical path finding problems, the cost of a search function is simply the number of queries made to an oracle that knows the position of the goal. In many problems, we want to charge a cost proportional to the distance between queries (e.g., the time required to travel between two query points). With this cost function in mind, the original *w*-lane cow-path problem [8] was modeled as a navigation problem in a terrain which consists of *w*-concurrent avenues. In this paper we study a variant of this problem where the terrain is an uniform *b-ary* tree, and there is a lower-bound estimate of the cost function. We present a strategy *CowP* for this class of problems where the relative error is bounded by a known constant and show that its worst case complexity is less than or equal to [*4b/(b−1)*] times optimal.

Item Type: | Conference or Workshop Item (Paper) |
---|---|

Source: | Copyright of this article belongs to Springer-Verlag Berlin Heidelberg. |

ID Code: | 102334 |

Deposited On: | 09 Mar 2018 10:15 |

Last Modified: | 09 Mar 2018 10:15 |

Repository Staff Only: item control page