{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:12Z","timestamp":1759639092620,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,6,20]],"date-time":"2016-06-20T00:00:00Z","timestamp":1466380800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-BS02-0015"],"award-info":[{"award-number":["ANR-11-BS02-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s00224-016-9691-3","type":"journal-article","created":{"date-parts":[[2016,6,20]],"date-time":"2016-06-20T01:41:21Z","timestamp":1466386881000},"page":"637-670","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Multi-processor Search and Scheduling Problems with Setup Cost"],"prefix":"10.1007","volume":"60","author":[{"given":"Spyros","family":"Angelopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diogo","family":"Ars\u00e9nio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"D\u00fcrr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,20]]},"reference":[{"key":"9691_CR1","unstructured":"Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Kluwer Academic Publishers (2003)"},{"key":"9691_CR2","unstructured":"Angelopoulos, S\/: Further connections between contract-scheduling and ray-searching problems. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1516\u20131522 (2015)"},{"key":"9691_CR3","unstructured":"Angelopoulos, S., Ars\u00e9nio, D., D\u00fcrr, C.: Infinite linear programming and the online search problem with turn cost. Manuscript. Available at http:\/\/www-desir.lip6.fr\/durrc\/bib\/turn.pdf"},{"key":"9691_CR4","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2014.03.028","volume":"540","author":"S Angelopoulos","year":"2014","unstructured":"Angelopoulos, S., L\u00f3pez-Ortiz, A., Panagiotou, K.: Multi-target ray searching problems. Theor. Comput. Sci. 540, 2\u201312 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9691_CR5","doi-asserted-by":"crossref","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.: Searching in the plane. Inf. Comput. 106, 234\u2013244 (1993)","journal-title":"Inf. Comput."},{"key":"9691_CR6","first-page":"221","volume":"2","author":"A Beck","year":"1964","unstructured":"Beck, A.: On the linear search problem. Nav. Res. Logist. 2, 221\u2013228 (1964)","journal-title":"Nav. Res. Logist."},{"key":"9691_CR7","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/BF02798690","volume":"8","author":"A Beck","year":"1970","unstructured":"Beck, A., Newman, D.J.: Yet more on the linear search problem. Israel J. Math. 8, 419\u2013429 (1970)","journal-title":"Israel J. Math."},{"key":"9691_CR8","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1137\/1005070","volume":"5","author":"R Bellman","year":"1963","unstructured":"Bellman, R.: An optimal search problem. SIAM Rev. 5, 274 (1963)","journal-title":"SIAM Rev."},{"key":"9691_CR9","doi-asserted-by":"crossref","unstructured":"Berman, P.: Online Algorithms: the State of the Art, chapter Online Searching and Navigation, pp. 232\u2013241. Springer (1998)","DOI":"10.1007\/BFb0029571"},{"key":"9691_CR10","unstructured":"Bernstein, D.S., Finkelstein, L., Zilberstein, S.: 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 (2003)"},{"key":"9691_CR11","unstructured":"Bernstein, D.S., Perkins, T.J., Zilberstein, S., Finkelstein, L.: Scheduling contract algorithms on multiple processors. In: Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI), pp. 702\u2013706 (2002)"},{"key":"9691_CR12","doi-asserted-by":"crossref","unstructured":"Bose, P., De Carufel, J., Durocher, S.: Revisiting the problem of searching on a line. In: Proceedings of the 21st European Symposium on Algorithms (ESA), pp. 205\u2013216 (2013)","DOI":"10.1007\/978-3-642-40450-4_18"},{"key":"9691_CR13","unstructured":"Dean, T., Boddy, M.S.: An analysis of time-dependent planning. In: Proceedings of the 7th National Conference on Artificial Intelligence, pp. 49\u201354 (1988)"},{"key":"9691_CR14","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.tcs.2006.05.018","volume":"361","author":"ED Demaine","year":"2006","unstructured":"Demaine, E.D., Fekete, S.P., Gal, S.: Online searching with turn cost. Theor. Comput. Sci. 361, 342\u2013355 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9691_CR15","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/BF02764811","volume":"12","author":"S Gal","year":"1972","unstructured":"Gal, S.: A general search game. Israel J. Math. 12, 32\u201345 (1972)","journal-title":"Israel J. Math."},{"key":"9691_CR16","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1137\/0127002","volume":"27","author":"S Gal","year":"1974","unstructured":"Gal, S.: Minimax solutions for linear search problems. SIAM J. App. Math. 27, 17\u201330 (1974)","journal-title":"SIAM J. App. Math."},{"key":"9691_CR17","unstructured":"Horvitz, E.: Reasoning about beliefs and actions under computational resource constraints. In: Proceedings of the Third Annual Conference on Uncertainty in Artificial Intelligence (UAI), pp. 301\u2013324 (1987)"},{"key":"9691_CR18","unstructured":"Horvitz, E.: Reasoning under varying and uncertain resource constraints. In: Proceedings of the 7th National Conference on Artificial Intelligence (AAAI), pp. 111\u2013116 (1998)"},{"key":"9691_CR19","first-page":"234","volume":"49","author":"P Jaillet","year":"1993","unstructured":"Jaillet, P., Stafford, M.: Online searching. Oper. Res. 49, 234\u2013244 (1993)","journal-title":"Oper. Res."},{"issue":"1","key":"9691_CR20","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1006\/jagm.1998.0959","volume":"29","author":"M-Y Kao","year":"1998","unstructured":"Kao, M.-Y., Ma, Y., Sipser, M., Yin, Y.L.: Optimal constructions of hybrid algorithms. J. Algoritm. 29(1), 142\u2013164 (1998)","journal-title":"J. Algoritm."},{"issue":"1","key":"9691_CR21","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"M-Y Kao","year":"1996","unstructured":"Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. Inform. Comp. 131(1), 63\u201380 (1996)","journal-title":"Inform. Comp."},{"key":"9691_CR22","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G.: Hyperbolic dovetailing. In: Proceedings of the 17th Annual European Symposium on Algorithms (ESA), pp. 616\u2013627 (2009)","DOI":"10.1007\/978-3-642-04128-0_46"},{"key":"9691_CR23","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G., Zilles, S.: Competitive search in symmetric trees. WADS, New York (2011)","DOI":"10.1007\/978-3-642-22300-6_47"},{"key":"9691_CR24","unstructured":"L\u00f3pez-Ortiz, A., Angelopoulos, S., Hamel, A.M.: Optimal scheduling of contract algorithms for anytime problems. In: Proceedings of the 21st National Conference on Artificial Intelligence (AAAI) (2006)"},{"issue":"2","key":"9691_CR25","doi-asserted-by":"crossref","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.: The ultimate strategy to search on m rays. Theor. Comput. Sci. 261(2), 267\u2013295 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"9691_CR26","doi-asserted-by":"crossref","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.: On-line parallel heuristics, processor scheduling and robot searching under the competitive framework. Theor. Comp. Sci. 310(1\u20133), 527\u2013537 (2004)","journal-title":"Theor. Comp. Sci."},{"key":"9691_CR27","doi-asserted-by":"crossref","unstructured":"McGregor, A., Onak, K., Panigrahy, R.: The oil searching problem. In: Proceedings of the 17th European Symposium on Algorithms (ESA), pp. 504\u2013515 (2009)","DOI":"10.1007\/978-3-642-04128-0_45"},{"key":"9691_CR28","unstructured":"Russell, S.J., Zilberstein, S.: Composing real-time systems. In: Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI), pp. 212\u2013217 (1991)"},{"issue":"3","key":"9691_CR29","first-page":"73","volume":"17","author":"S Zilberstein","year":"1996","unstructured":"Zilberstein, S.: Using anytime algorithms in intelligent systems. AI Mag. 17 (3), 73\u201383 (1996)","journal-title":"AI Mag."},{"issue":"1\u20132","key":"9691_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1023\/A:1024412831598","volume":"39","author":"S Zilberstein","year":"2003","unstructured":"Zilberstein, S., Charpillet, F., Chassaing, P.: Real-time problem-solving with contract algorithms. Ann. Math. Artif. Intell. 39(1\u20132), 1\u201318 (2003)","journal-title":"Ann. Math. Artif. Intell."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9691-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9691-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9691-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9691-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T12:42:26Z","timestamp":1498308146000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9691-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,20]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["9691"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9691-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2016,6,20]]}}}