{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T21:13:55Z","timestamp":1762809235884,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T00:00:00Z","timestamp":1643241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this paper, we introduce a linear program (LP)-based formulation of a rendezvous game with markers on the infinite line and solve it. In this game one player moves at unit speed while the second player moves at a speed bounded by vmax\u22641. We observe that in this setting, a slow-moving player may have interest to remain still instead of moving. This shows that in some conditions the wait-for-mummy strategy is optimal. We observe as well that the strategies are completely different if the player that holds the marker is the fast or slow one. Interestingly, the marker is not useful when the player without marker moves slowly, i.e., the fast-moving player holds the marker.<\/jats:p>","DOI":"10.3390\/a15020041","type":"journal-article","created":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T21:59:55Z","timestamp":1643320795000},"page":"41","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Rendezvous on the Line with Different Speeds and Markers That Can Be Dropped at Chosen Time"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4514-5380","authenticated-orcid":false,"given":"Pierre","family":"Leone","sequence":"first","affiliation":[{"name":"TCS-Sensor Lab, Centre Universitaire d\u2019Informatique, Battelle Batiment A, Route de Drize 7, CH-1227 Carouge, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Cohen","sequence":"additional","affiliation":[{"name":"TCS-Sensor Lab, Centre Universitaire d\u2019Informatique, Battelle Batiment A, Route de Drize 7, CH-1227 Carouge, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1270","DOI":"10.1137\/S0363012993260288","article-title":"Rendezvous search on the line with distinguishable players","volume":"33","author":"Alpern","year":"1995","journal-title":"SIAM J. Control Optim."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S0363012993249195","article-title":"The Rendezvous Search Problem","volume":"33","author":"Alpern","year":"1995","journal-title":"SIAM J. Control Optim."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1637","DOI":"10.1137\/S0363012993260707","article-title":"Rendezvous Search on the Line with Indistinguishable Players","volume":"33","author":"Anderson","year":"1995","journal-title":"SIAM J. Control Optim."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1002\/(SICI)1520-6750(199904)46:3<335::AID-NAV6>3.0.CO;2-Q","article-title":"Note: Two rendezvous search problems on the line","volume":"46","author":"Baston","year":"1999","journal-title":"Nav. Res. Logist."},{"key":"ref_5","unstructured":"Uthaisombut, P. (2021, December 14). Symmetric Rendezvous Search on the Line Using Move Patterns with Different Lengths. Citeseer. Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.59.6033."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"772","DOI":"10.1287\/opre.1070.0439","article-title":"Improved Bounds for the Symmetric Rendezvous Value on the Line","volume":"56","author":"Han","year":"2008","journal-title":"Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1880","DOI":"10.1137\/S0363012996314130","article-title":"Rendezvous on the Line when the Players\u2019 Initial Distance is Given by an Unknown Probability Distribution","volume":"36","author":"Baston","year":"1998","journal-title":"SIAM J. Control Optim."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.47.6.849","article-title":"Rendezvous Search on the Line with Limited Resources: Maximizing the Probability of Meeting","volume":"47","author":"Alpern","year":"1999","journal-title":"Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.48.3.498.12432","article-title":"Pure Strategy Asymmetric Rendezvous on the Line with an Unknown Initial Distance","volume":"48","author":"Alpern","year":"2000","journal-title":"Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1366","DOI":"10.1109\/TRO.2013.2272252","article-title":"Symmetric Rendezvous Search on the Line With an Unknown Initial Distance","volume":"29","author":"Ozsoyeller","year":"2013","journal-title":"IEEE Trans. Robot."},{"key":"ref_11","unstructured":"Stachowiak, G. (2009, January 24\u201330). Asynchronous deterministic rendezvous on the line. Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science, \u0160pindleruv Ml\u00fdn, Czech Republic."},{"key":"ref_12","unstructured":"Czyzowicz, J., Killick, R., and Kranakis, E. (2018, January 17\u201319). Linear rendezvous with asymmetric clocks. Proceedings of the 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Hong Kong, China."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Chrobak, M., G\u0105sieniec, L., Gorry, T., and Martin, R. (2015, January 24\u201329). Group search on the line. Proceedings of the International Conference on Current Trends in Theory and Practice of Informatics, Pecpod Sne\u017ekou, Czech Republic.","DOI":"10.1007\/978-3-662-46078-8_14"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1287\/opre.47.4.550","article-title":"Rendezvous Search on the Interval and the Circle","volume":"47","author":"Howard","year":"1999","journal-title":"Oper. Res."},{"key":"ref_15","unstructured":"Kranakis, E., Santoro, N., Sawchuk, C., and Krizanc, D. (2003, January 19\u201322). Mobile agent rendezvous in a ring. Proceedings of the 23rd International Conference on Distributed Computing Systems, Providence, RI, USA."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Kranakis, E., Krizanc, D., Santoro, N., and Sawchuk, C. (2004). Multiple mobile agent rendezvous in a ring. Latin American Symposium on Theoretical Informatics, Springer.","DOI":"10.1007\/978-3-540-27796-5_15"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-031-01999-9","article-title":"The mobile agent rendezvous problem in the ring","volume":"1","author":"Kranakis","year":"2010","journal-title":"Synth. Lect. Distrib. Comput. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s00446-016-0278-7","article-title":"Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings","volume":"30","author":"Navarra","year":"2017","journal-title":"Distrib. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Dobrev, S., Kranakis, E., and Krizanc, D. (2008, January 19\u201325). The power of tokens: Rendezvous and symmetry detection for two mobile agents in a ring. Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science, Nov\u00fd Smokovec, Slovakia.","DOI":"10.1007\/978-3-540-77566-9_20"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Kranakis, E., Krizanc, D., Luccio, F.L., Santoro, N., and Sawchuk, C. (2004). Mobile agents rendezvous when tokens fail. International Colloquium on Structural Information and Communication Complexity, Springer.","DOI":"10.1007\/978-3-540-27796-5_15"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Das, S., Mihal\u00e1k, M., \u0160r\u00e1mek, R., Vicari, E., and Widmayer, P. (2008, January 15\u201318). Rendezvous of mobile agents when tokens fail anytime. Proceedings of the International Conference on Principles of Distributed Systems, Luxor, Egypt.","DOI":"10.1007\/978-3-540-92221-6_29"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"722","DOI":"10.1002\/nav.1044","article-title":"Rendezvous search when marks are left at the starting points","volume":"48","author":"Baston","year":"2001","journal-title":"Nav. Res. Logist."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1002\/nav.21818","article-title":"Rendezvous Search With Markers That Can Be Dropped at Chosen Times","volume":"65","author":"Leone","year":"2018","journal-title":"Nav. Res. Logist."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Das, S., Luccio, F.L., and Markou, E. (2015, January 17\u201318). Mobile agents rendezvous in spite of a malicious agent. Proceedings of the International Symposium on Algorithms and Experiments for Wireless Sensor Networks, Patras, Greece.","DOI":"10.1007\/978-3-319-28472-9_16"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.tcs.2018.05.002","article-title":"Gathering of robots in a ring with mobile faults","volume":"764","author":"Das","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_26","unstructured":"Alpern, S., and Gal, S. (2006). The Theory of Search Games and Rendezvous, Springer."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Alpern, S. (2013). Ten open problems in rendezvous search. Search Theory, Springer.","DOI":"10.1007\/978-1-4614-6825-7"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Pelc, A. (2019). Deterministic Rendezvous Algorithms. Distributed Computing by Mobile Entities, Springer.","DOI":"10.1007\/978-3-030-11072-7_17"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1153","DOI":"10.1016\/j.ejor.2020.02.029","article-title":"Search and rescue in the face of uncertain threats","volume":"285","author":"Lidbetter","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s00182-014-0432-z","article-title":"Search games on a network with travelling and search costs","volume":"44","author":"Baston","year":"2015","journal-title":"Int. J. Game Theory"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/j.ejor.2019.02.029","article-title":"A search problem on a bipartite network","volume":"277","author":"Baston","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1002\/net.21504","article-title":"Search games on networks with travelling and search costs and with arbitrary searcher starting points","volume":"62","author":"Baston","year":"2013","journal-title":"Networks"},{"key":"ref_33","first-page":"1","article-title":"Search games: Literature and survey","volume":"59","author":"Hohzaki","year":"2016","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Alpern, S., Fokkink, R., Gasieniec, L., Lindelauf, R., and Subrahmanian, V. (2013). Search Theory, Springer.","DOI":"10.1007\/978-1-4614-6825-7"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1287\/moor.24.3.604","article-title":"Asymmetric rendezvous on the line is a double linear search problem","volume":"24","author":"Alpern","year":"1999","journal-title":"Math. Oper. Res."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1016\/j.ejor.2021.05.009","article-title":"Search-and-Rescue Rendezvous","volume":"297","author":"Leone","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_37","unstructured":"Isaacs, R. (1999). Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization, Courier Corporation."},{"key":"ref_38","unstructured":"Mehlmann, A. (2013). Applied Differential Games, Springer."},{"key":"ref_39","unstructured":"Friedman, A. (2013). Differential Games, Courier Corporation."},{"key":"ref_40","unstructured":"(2021). Gurobi Optimizer Reference Manual, Gurobi Optimization, LLC."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/41\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:08:50Z","timestamp":1760134130000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,27]]},"references-count":40,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020041"],"URL":"https:\/\/doi.org\/10.3390\/a15020041","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,1,27]]}}}