Improved bounds for the symmetric rendezvous value on the line

ABSTRACT

A notorious open problem in the field of rendezvous search is to decide the rendezvous value of the symmetric rendezvous search problem on the line, when the initial distance apart between the two players is 2. We show that the symmetric rendezvous value is within the interval (4.1520, 4.2574), which considerably improves the previous best known result (3.9546, 4.3931). To achieve the improved bounds, we call upon results from absorbing markov chain theory and mathematical programming theory---particularly fractional quadratic programming and semidefinite programming. Moreover, we also establish some important properties of this problem, which may be of independent interest and useful for resolving this problem completely. Finally, we conjecture that the symmetric rendezvous value is asymptotically equal to 4.25 based on our numerical calculations.

REFERENCES

• 1: Steve Alpern, The Rendezvous Search Problem, SIAM Journal on Control and Optimization, v.33 n.3, p.673-683, May 1995 [doi>10.1137/S0363012993249195]
• 2: Steve Alpern, Rendezvous Search: A Personal Perspective, Operations Research, v.50 n.5, p.772-795, September 2002 [doi>10.1287/opre.50.5.772.363]
• 3: S. Alpern and S. Beck, Rendezvous search problem on the line with bounded resources: Expected time minimization. Eur J Oper Res, 101 (1997), 588--597.
• 4: Steve Alpern , Anatole Beck, Asymmetric Rendezvous on the Line is a Double Linear Search Problem, Mathematics of Operations Research, v.24 n.3, p.604-618, August 1999 [doi>10.1287/moor.24.3.604]
• 5: Steve Alpern , Anatole Beck, Rendezvous Search on the Line with Limited Resources: Maximizing the Probability of Meeting, Operations Research, v.47 n.6, p.849-861, June 1999 [doi>10.1287/opre.47.6.849]
• 6: Steve Alpern , Anatole Beck, Pure Strategy Asymmetric Rendezvous on the Line with an Unknown Initial Distance, Operations Research, v.48 n.3, p.498-501, May 2000 [doi>10.1287/opre.48.3.498.12432]
• 7: Edward J. Anderson , Skander Essegaier, Rendezvous Search on the Line with Indistinguishable Players, SIAM Journal on Control and Optimization, v.33 n.6, p.1637-1642, Nov. 1995 [doi>10.1137/S0363012993260707]
• 8: Steve Alpern, The Rendezvous Search Problem, SIAM Journal on Control and Optimization, v.33 n.3, p.673-683, May 1995 [doi>10.1137/S0363012993249195]
• 9: S. Alpern and S. Gal, The theory of search games and rendezvous. Kluwer Academic Publishers, 2003.
• 10: S. Alpern and S. Gal, private communication, 2006.
• 11: V. J. Baston, Two rendezvous search problems on the line, Naval Res Logist. 46 (1999), 335--340.
• 12: S. J. Benson and Y. Ye. DSDP5: Software for semidefinite programming. Technical Report ANL/MCSP 1289--0905, Mathematics and Computer Science Division, Argonne National Laboratory, September 2005. http://www-unix.mcs.anl.gov/DSDP/.
• 13: W. Feller, An introduction to probability theory and its applications. Volume 1, Wiley, 1950, 307--344.
• 14: Arthur Hsu , Yehuda Bassok , Nicolas P. B. Bollen , Liqun Qi , Scott Webster , J. V. Howard , Shmuel Gal, Rendezvous Search on the Line, Operations Research, v.47 n.6, p.974-976, June 1999 [doi>10.1287/opre.47.6.974]
• 15: W. S. Lim, A. Beck, and S. Alpern, Rendezvous search on the line with more than two players. Oper. Res. 45(3) (1997) 357--364.
• 16: Carl D. Meyer, Matrix analysis and applied linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 17: G. Pólya, How to solve it: a new aspect of mathematical method, 2nd Ed., Princeton University Press, Princeton NJ, 1957.
• 18: J. F. Sturm, Using SeDuMi 1.02, a matlab toolbox for optimization over symmetric cones. Optim. Methods and Softw. 11--12 (1999), 625--653.
• 19: P. Uthaisombut, Symmetric rendezvous search on the line using moving patterns with different lengths. Working paper, Department of Computer Science, University of Pittsburgh, 2006.