{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T03:25:30Z","timestamp":1775791530686,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T00:00:00Z","timestamp":1636588800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T00:00:00Z","timestamp":1636588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s10951-021-00712-8","type":"journal-article","created":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T10:02:26Z","timestamp":1636624946000},"page":"139-155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Further connections between contract-scheduling and ray-searching problems"],"prefix":"10.1007","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9819-9158","authenticated-orcid":false,"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,11,11]]},"reference":[{"key":"712_CR1","unstructured":"Alpern, S., & Gal, S. (2003). The theory of search games and rendezvous. Kluwer Academic Publishers."},{"issue":"2","key":"712_CR2","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1287\/opre.1120.1134","volume":"61","author":"S Alpern","year":"2013","unstructured":"Alpern, S., & Lidbetter, T. (2013). Mining coal or finding terrorists: The expanding search paradigm. Operations Research, 61(2), 265\u2013279.","journal-title":"Operations Research"},{"key":"712_CR3","unstructured":"Angelopoulos, S. (2015). Further connections between contract-scheduling and ray-searching problems. In Proceedings of the Twenty-fourth International Joint Conference on Artificial Intelligence, IJCAI, 2015 (pp. 1516\u20131522)."},{"key":"712_CR4","unstructured":"Angelopoulos, S. (2021). Online search with a hint. In J. R. Lee (Ed.), 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, LIPIcs (Vol. 185, pp. 51:1-51:16). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"key":"712_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.tcs.2017.01.013","volume":"670","author":"S Angelopoulos","year":"2017","unstructured":"Angelopoulos, S., Ars\u00e9nio, D., & D\u00fcrr, C. (2017). Infinite linear programming and online searching with turn cost. Theoretical Computer Science, 670, 11\u201322.","journal-title":"Theoretical Computer Science"},{"key":"712_CR6","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.dam.2019.01.039","volume":"260","author":"S Angelopoulos","year":"2019","unstructured":"Angelopoulos, S., D\u00fcrr, C., & Lidbetter, T. (2019). The expanding search ratio of a graph. Discrete Applied Mathematics, 260, 51\u201365.","journal-title":"Discrete Applied Mathematics"},{"key":"712_CR7","doi-asserted-by":"crossref","unstructured":"Angelopoulos, S., & Jin, S. (2019). Earliest completion scheduling of contract algorithms with end guarantees. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI) (pp. 5493\u20135499)","DOI":"10.24963\/ijcai.2019\/763"},{"key":"712_CR8","unstructured":"Angelopoulos, S., & L\u00f3pez-Ortiz, A. (2009). Interruptible algorithms for multi-problem solving. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI) (pp. 380\u2013386)."},{"key":"712_CR9","unstructured":"Angelopoulos, S., L\u00f3pez-Ortiz, A., & Hamel, A. (2008). Optimal scheduling of contract algorithms with soft deadlines. In Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI) (pp. 868\u2013873)."},{"key":"712_CR10","unstructured":"Angelopoulos, S., & Panagiotou, K. (2017). Optimal strategies for weighted ray search. CoRR. http:\/\/arxiv.org\/abs\/1704.03777"},{"key":"712_CR11","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R Baeza-Yates","year":"1993","unstructured":"Baeza-Yates, R., Culberson, J., & Rawlins, G. (1993). Searching in the plane. Information and Computation, 106, 234\u2013244.","journal-title":"Information and Computation"},{"key":"712_CR12","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF02798690","volume":"8","author":"A Beck","year":"1970","unstructured":"Beck, A., & Newman, D. (1970). Yet more on the linear search problem. Israel Journal of Mathematics, 8, 419\u2013429.","journal-title":"Israel Journal of Mathematics"},{"key":"712_CR13","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/1005070","volume":"5","author":"R Bellman","year":"1963","unstructured":"Bellman, R. (1963). An optimal search problem. SIAM Review, 5, 274.","journal-title":"SIAM Review"},{"key":"712_CR14","unstructured":"Bernstein, D., Finkelstein, L., & Zilberstein, S. (2003). Contract algorithms and robots on rays: Unifying two scheduling problems. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI) (pp. 1211\u20131217)."},{"key":"712_CR15","unstructured":"Bernstein, D., Perkins, T.J., Zilberstein, S., & Finkelstein, L. (2002). Scheduling contract algorithms on multiple processors. In Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI) (pp. 702\u2013706)."},{"key":"712_CR16","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2018.10.032","volume":"811","author":"S Brandt","year":"2020","unstructured":"Brandt, S., Foerster, K. T., Richner, B., & Wattenhofer, R. (2020). Wireless evacuation on m rays with k searchers. Theoretical Computer Science, 811, 56\u201369.","journal-title":"Theoretical Computer Science"},{"key":"712_CR17","doi-asserted-by":"crossref","unstructured":"Chrobak, M., Gasieniec, L., Gorry, T., & Martin, R. (2015). Group search on the line. In International Conference on Current Trends in Theory and Practice of Informatics (pp. 164\u2013176). Springer.","DOI":"10.1007\/978-3-662-46078-8_14"},{"issue":"4","key":"712_CR18","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10514-011-9241-4","volume":"31","author":"TH Chung","year":"2011","unstructured":"Chung, T. H., Hollinger, G. A., & Isler, V. (2011). Search and pursuit-evasion in mobile robotics. Autonomous Robots, 31(4), 299.","journal-title":"Autonomous Robots"},{"issue":"2","key":"712_CR19","first-page":"24:1","volume":"5","author":"A Condon","year":"2009","unstructured":"Condon, A., Deshpande, A., Hellerstein, L., & Wu, N. (2009). Algorithms for distributional and adversarial pipelined filter ordering problems. ACM Transaction on Algorithms, 5(2), 24:1-24:34.","journal-title":"ACM Transaction on Algorithms"},{"key":"712_CR20","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.tcs.2006.05.018","volume":"361","author":"E Demaine","year":"2006","unstructured":"Demaine, E., Fekete, S., & Gal, S. (2006). Online searching with turn cost. Theoretical Computer Science, 361, 342\u2013355.","journal-title":"Theoretical Computer Science"},{"key":"712_CR21","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BF02764811","volume":"12","author":"S Gal","year":"1972","unstructured":"Gal, S. (1972). A general search game. Israel Journal of Mathematics, 12, 32\u201345.","journal-title":"Israel Journal of Mathematics"},{"key":"712_CR22","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1137\/0127002","volume":"27","author":"S Gal","year":"1974","unstructured":"Gal, S. (1974). Minimax solutions for linear search problems. SIAM Journal on Applied Mathematics, 27, 17\u201330.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"712_CR23","first-page":"234","volume":"49","author":"P Jaillet","year":"1993","unstructured":"Jaillet, P., & Stafford, M. (1993). Online searching. Operations Research, 49, 234\u2013244.","journal-title":"Operations Research"},{"key":"712_CR24","unstructured":"Kao, M. Y., & Littman, M. (1997). Algorithms for informed cows. In Proceedings of the AAAI 1997 Workshop on Online Search."},{"issue":"1","key":"712_CR25","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1006\/jagm.1998.0959","volume":"29","author":"MY Kao","year":"1998","unstructured":"Kao, M. Y., Ma, Y., Sipser, M., & Yin, Y. (1998). Optimal constructions of hybrid algorithms. Journal of Algorithms, 29(1), 142\u2013164.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"712_CR26","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"MY Kao","year":"1996","unstructured":"Kao, M. Y., Reif, J., & Tate, S. (1996). Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Information and Computation, 131(1), 63\u201380.","journal-title":"Information and Computation"},{"key":"712_CR27","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D. G. (2009). Hyperbolic dovetailing. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA) (pp. 616\u2013627).","DOI":"10.1007\/978-3-642-04128-0_46"},{"key":"712_CR28","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C., & Yannakakis, M.: (1996). Searching a fixed graph. In Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP) (pp. 280\u2013289).","DOI":"10.1007\/3-540-61440-0_135"},{"key":"712_CR29","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1613\/jair.4360","volume":"51","author":"A L\u00f3pez-Ortiz","year":"2014","unstructured":"L\u00f3pez-Ortiz, A., Angelopoulos, S., & Hamel, A. (2014). Optimal scheduling of contract algorithms for anytime problems. Journal of Artificial Intelligence Research, 51, 533\u2013554.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2","key":"712_CR30","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/S0304-3975(00)00144-4","volume":"261","author":"A L\u00f3pez-Ortiz","year":"2001","unstructured":"L\u00f3pez-Ortiz, A., & Schuierer, S. (2001). The ultimate strategy to search on $$m$$ rays. Theoretical Computer Science, 261(2), 267\u2013295.","journal-title":"Theoretical Computer Science"},{"issue":"1\u20133","key":"712_CR31","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1016\/j.tcs.2003.08.001","volume":"310","author":"A L\u00f3pez-Ortiz","year":"2004","unstructured":"L\u00f3pez-Ortiz, A., & Schuierer, S. (2004). On-line parallel heuristics, processor scheduling and robot searching under the competitive framework. Theoretical Computer Science, 310(1\u20133), 527\u2013537.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"712_CR32","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1080\/00029890.1964.11992194","volume":"71","author":"D Matula","year":"1964","unstructured":"Matula, D. (1964). A periodic optimal search. The American Mathematical Monthly, 71(1), 15\u201321.","journal-title":"The American Mathematical Monthly"},{"key":"712_CR33","doi-asserted-by":"crossref","unstructured":"McGregor, A., Onak, K., & Panigrahy, R. (2009). The oil searching problem. In Proceedings of the 17th European Symposiumon Algorithms (ESA) (pp. 504\u2013515).","DOI":"10.1007\/978-3-642-04128-0_45"},{"key":"712_CR34","first-page":"9661","volume":"31","author":"M Purohit","year":"2018","unstructured":"Purohit, M., Svitkina, Z., & Kumar, R. (2018). Improving online algorithms via ML predictions. Advances in Neural Information Processing Systems, 31, 9661\u20139670.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"712_CR35","unstructured":"Russell, S. J., & Zilberstein, S. (1991). Composing real-time systems. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI) (pp. 212\u2013217)."},{"issue":"1","key":"712_CR36","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0925-7721(00)00030-4","volume":"18","author":"S Schuierer","year":"2001","unstructured":"Schuierer, S. (2001). Lower bounds in online geometric searching. Computational Geometry: Theory and Applications, 18(1), 37\u201353.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"712_CR37","doi-asserted-by":"crossref","unstructured":"Schuierer, S. (2003). A lower bound for randomized searching on m rays. In R. Klein, H. W. Six, & L. Wegner (Eds.), Computer science in perspective (pp. 264\u2013277). Springer.","DOI":"10.1007\/3-540-36477-3_20"},{"key":"712_CR38","unstructured":"Zilberstein, S. (1996). Using anytime algorithms in intelligent systems. AI Magazine, 17(3), 73\u201383."},{"issue":"1\u20132","key":"712_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1024412831598","volume":"39","author":"S Zilberstein","year":"2003","unstructured":"Zilberstein, S., Charpillet, F., & Chassaing, P. (2003). Real-time problem-solving with contract algorithms. Annals of Mathematics and Artificial Intelligence, 39(1\u20132), 1\u201318.","journal-title":"Annals of Mathematics and Artificial Intelligence"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00712-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-021-00712-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00712-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,22]],"date-time":"2022-04-22T07:25:27Z","timestamp":1650612327000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-021-00712-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,11]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["712"],"URL":"https:\/\/doi.org\/10.1007\/s10951-021-00712-8","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,11]]},"assertion":[{"value":"9 October 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}