4 papers
On the Cyclic Assumption of the Cow-Path Search Algorithm
Yuan Ma, Yiqun Lisa Yin
In the cow-path problem, a cow must find a goal lying at an unknown distance on one of paths connected only at the origin, and performance is measured by competitive ratio. Kao…
On Searching a Table Consistent with Division Poset
Yongxi Cheng, Xi Chen, Yiqun Lisa Yin
Suppose is a partially ordered set with the partial order defined by divisibility, that is, for any two distinct elements satisfying divides $j…
Searching Monotone Multi-dimensional Arrays
Yongxi Cheng, Xiaoming Sun, Yiqun Lisa Yin
In this paper we investigate the problem of searching monotone multi-dimensional arrays. We generalize Linial and Saks' search algorithm \cite{LS1} for monotone 3-dimensional array…
Optimal Constructions of Hybrid Algorithms
Ming-Yang Kao, Yuan Ma, Michael Sipser +1
We study on-line strategies for solving problems with hybrid algorithms. There is a problem Q and w basic algorithms for solving Q. For some lambda <= w, we have a computer with la…