{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T16:01:23Z","timestamp":1773763283231,"version":"3.50.1"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Berlin Mathematics Research Center","award":["EXC-2046\/1"],"award-info":[{"award-number":["EXC-2046\/1"]}]},{"name":"Berlin Mathematics Research Center","award":["390685689"],"award-info":[{"award-number":["390685689"]}]},{"name":"Centro de Modelamiento Matematico","award":["FB210005"],"award-info":[{"award-number":["FB210005"]}]},{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["DFF-0135-00018B"],"award-info":[{"award-number":["DFF-0135-00018B"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008001","name":"Universit\u00e4t zu K\u00f6ln","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2026,3,31]]},"DOI":"10.1137\/25m1759902","type":"journal-article","created":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T14:08:36Z","timestamp":1773756516000},"page":"349-373","source":"Crossref","is-referenced-by-count":0,"title":["Improved Approximation Algorithms for the Expanding Search Problem"],"prefix":"10.1137","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8018-3289","authenticated-orcid":true,"given":"Svenja M.","family":"Griesbach","sequence":"first","affiliation":[{"name":"Faculty of Computer Science, RWTH Aachen University, Aachen, Germany; Centro de Modelamiento Matem\u00e1tico CNRS IRL2807Universidad de Chile, Santiago, Chile."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4444-9793","authenticated-orcid":true,"given":"Felix","family":"Hommelsheim","sequence":"additional","affiliation":[{"name":"University of Cologne, Department of Mathematics and Computer Science, Cologne, Germany; Universit\u00e4t Bremen, Faculty of Mathematics and Computer Science, Bremen, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9061-2267","authenticated-orcid":true,"given":"Max","family":"Klimm","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Institute for Mathematics, Berlin, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2236-0210","authenticated-orcid":true,"given":"Kevin","family":"Schewior","sequence":"additional","affiliation":[{"name":"University of Cologne, Department of Mathematics and Computer Science, Cologne, Germany; University of Southern Denmark, Department of Mathematics and Computer Science, Odense, Denmark."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","published-online":{"date-parts":[[2026,3,17]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/0206002"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1986200100791"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6825-7"},{"key":"ref4","series-title":"Int. Ser. Oper. Res. Manag. Sci. 55","volume-title":"The Theory of Search Games and Rendezvous","author":"Alpern S.","year":"2003"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1134"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-018-2966-0"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.01.039"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"A. Archer and A. Blasiak, Improved approximation algorithms for the minimum latency problem via prize-collecting strolls, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2010, pp. 429\u2013447.","DOI":"10.1137\/1.9781611973075.36"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/07068151X"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701399654"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2012.01.001"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1080\/0740817X.2011.636792"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Chalasani, D. Coppersmith, W. R. Pulleyblank, P. Raghavan, and M. Sudan, The minimum latency problem, in Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1994, pp. 163\u2013171.","DOI":"10.1145\/195058.195125"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar, Paths, trees, and minimum latency tours, in Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, Los Alamitos, CA, 2003, pp. 36\u201345.","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"C. Chekuri and A. Kumar, Maximum coverage problem with group budget constraints and applications, in Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), Springer, Berlin, 2004, pp. 72\u201383.","DOI":"10.1007\/978-3-540-27821-4_7"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2013.01.003"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290677"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.6.1055"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/100797357"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/0317009"},{"key":"ref24","volume-title":"Search Games","author":"Gal S.","year":"1980"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1002\/net.10031"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"N. Garg, Saving an epsilon: A 2-approximation for the \\(k\\)-MST problem in graphs, in Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 2005, pp. 396\u2013402.","DOI":"10.1145\/1060590.1060650"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585867"},{"key":"ref28","unstructured":"S. M. Griesbach, F. Hommelsheim, M. Klimm, and K. Schewior, Improved approximation algorithms for the expanding search problem, in Proceedings of the Annual European Symposium on Algorithms (ESA), I. L. G\u00f8rtz, M. Farach-Colton, S. J. Puglisi, and G. Herman, eds. LIPIcs. Leibniz Int. Proc. Inform., Wadern, Germany, 2023, 54."},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2020.1047"},{"key":"ref30","volume-title":"Differential Games","author":"Isaacs R.","year":"1965"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"D. Kirkpatrick, Hyperbolic dovetailing, in Proceedings of the Annual European Symposium on Algorithms (ESA), Springer, Berlin, 2009, pp. 516\u2013527.","DOI":"10.1007\/978-3-642-04128-0_46"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"E. Koutsoupias, C. H. Papadimitriou, and M. Yannakakis, Searching a fixed graph, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), Springer, Berlin, 1996, pp. 280\u2013289.","DOI":"10.1007\/3-540-61440-0_135"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00409-7"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70323-6"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1002\/net.21793"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/BF02097807"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"V. Nagarajan and R. Ravi, The directed minimum latency problem, in Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), Springer, Berlin, 2008, pp. 193\u2013206.","DOI":"10.1007\/978-3-540-85363-3_16"},{"key":"ref38","unstructured":"R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz, and S. S. Ravi, Spanning trees short or small, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 1994, pp. 546\u2013555."},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"R. Sitters, The minimum latency problem is NP-hard for weighted trees, in Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO), Springer, Berlin, 2002, pp. 230\u2013239.","DOI":"10.1007\/3-540-47867-1_17"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1137\/19M126918X"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1109\/TPWRS.2019.2898966"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1287\/opre.34.2.324"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230220305"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T14:08:42Z","timestamp":1773756522000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1759902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,17]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1137\/25M1759902"],"URL":"https:\/\/doi.org\/10.1137\/25m1759902","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,17]]}}}