Arrow Research search

Author name cluster

Stephen R. Tate

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers
2 author rows

Possible papers

8

I&C Journal 1996 Journal Article

Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem

  • Ming-Yang Kao
  • John H. Reif
  • Stephen R. Tate

Searching for a goal is a central and extensively studied problem in computer science. In classical searching 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 robotics problems, as well as in problems from other areas, 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 abstract problem known as thew-lane cow-path problem was designed. There are known optimal deterministic algorithms for the cow-path problem; we give the first randomized algorithm in this paper. We show that our algorithm is optimal for two paths (w=2) and give evidence that it is optimal for larger values ofw. Subsequent to the preliminary version of this paper, Kaoet al. (in“Proceedings, 5th ACM–SIAM Symposium on Discrete Algorithm, ” pp. 372–381, 1994) have shown that our algorithm is indeed optimal for allw⩾2. Our randomized algorithm gives expected performance that is almost twice as good as is possible with a deterministic algorithm. For the performance of our algorithm, we also derive the asymptotic growth with respect tow—despite similar complexity results for related problems, it appears that this growth has never been analyzed.

Details DOI

FOCS Conference 1992 Conference Paper

The Power of Combining the Techiques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms

  • Victor Y. Pan
  • John H. Reif
  • Stephen R. Tate

The authors demonstrate the power of combining the techniques of algebraic computation with ones of numerical computation. They do this by improving the known methods for polynomial evaluation on a set of real points and for simulation of n charged particles on the plane. In both cases they approximate (rather than exactly compute) the solutions and do this by exploiting algebraic techniques of the algorithm design. >

Details
v2026.09.13