Dasgupta, Pallab ; Chakrabarti, P. P. ; DeSarkar, S. C. (1996) A new competitive algorithm for agent searching in unknown streets In: 16th Conference on Foundations of Software Technology and Theoretical Computer Science, 18–20 December 1996, Hyderabad, India.
Full text not available from this repository.
Official URL: http://link.springer.com/chapter/10.1007/3-540-620...
Related URL: http://dx.doi.org/10.1007/3-540-62034-6_45
Abstract
In this paper we present a simple on-line strategy based on a continuous angle bisector approach for searching an unknown street polygon. The proposed strategy achieves a competitive ratio of 1+loge(1+ cos α/2)+δ, where 0 ≤ α ≤ π, and δ is a given constant greater than zero. By choosing an arbitrarily small value for δ, the value of this ratio is 1.7, which is significantly better than the previous upperbound of 2.83 (derived by Kleinberg [6]), considering that the lowerbound for this problem is √2(> 1.41) (derived by Klein [5]).
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag Berlin Heidelberg. |
| ID Code: | 102336 |
| Deposited On: | 09 Mar 2018 10:13 |
| Last Modified: | 09 Mar 2018 10:13 |
Repository Staff Only: item control page
