{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T21:37:37Z","timestamp":1742938657129,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031813955"},{"type":"electronic","value":"9783031813962"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-81396-2_5","type":"book-chapter","created":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T21:14:14Z","timestamp":1739394854000},"page":"61-75","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating $$\\delta $$-Covering"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1028-6351","authenticated-orcid":false,"given":"Tim A.","family":"Hartmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4617-3540","authenticated-orcid":false,"given":"Tom","family":"Jan\u00dfen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,12]]},"reference":[{"issue":"3","key":"5_CR1","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979). https:\/\/doi.org\/10.1287\/moor.4.3.233","journal-title":"Math. Oper. Res."},{"key":"5_CR2","doi-asserted-by":"publisher","unstructured":"Crescenzi, P.: A short guide to approximation preserving reductions. In: Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, 24\u201327 June 1997, pp. 262\u2013273. IEEE Computer Society (1997). https:\/\/doi.org\/10.1109\/CCC.1997.612321","DOI":"10.1109\/CCC.1997.612321"},{"issue":"4","key":"5_CR3","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1287\/trsc.8.4.333","volume":"8","author":"PM Dearing","year":"1974","unstructured":"Dearing, P.M., Francis, R.L.: A minimax location problem on a network. Transp. Sci. 8(4), 333\u2013343 (1974)","journal-title":"Transp. Sci."},{"issue":"1","key":"5_CR4","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating vertex cover. Ann. Math. 162(1), 439\u2013485 (2005). https:\/\/doi.org\/10.4007\/annals.2005.162.439","journal-title":"Ann. Math."},{"issue":"11","key":"5_CR5","first-page":"1421","volume":"47","author":"E Drezner","year":"1996","unstructured":"Drezner, E.: Facility location: a survey of applications and methods. J. Oper. Res. Soc. 47(11), 1421\u20131421 (1996)","journal-title":"J. Oper. Res. Soc."},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"5_CR7","unstructured":"Gallai, T.: Kritische Graphen II. A Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei 8, 373\u2013395 (1963)"},{"key":"5_CR8","unstructured":"Gallai, T.: Maximale Systeme unabh\u00e4ngiger Kanten. A Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei 9, 401\u2013413 (1964)"},{"key":"5_CR9","doi-asserted-by":"publisher","unstructured":"Grigoriev, A., Hartmann, T.A., Lendl, S., Woeginger, G.J.: Dispersing obnoxious facilities on a graph. In: Niedermeier, R., Paul, C. (eds.) 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019. LIPIcs, 13\u201316 March 2019, Berlin, Germany, vol.\u00a0126, pp. 33:1\u201333:11. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.33","DOI":"10.4230\/LIPIcs.STACS.2019.33"},{"key":"5_CR10","doi-asserted-by":"publisher","unstructured":"Hartmann, T.A.: Facility location on graphs. Dissertation, RWTH Aachen University, Aachen (2022). https:\/\/doi.org\/10.18154\/RWTH-2023-01837","DOI":"10.18154\/RWTH-2023-01837"},{"key":"5_CR11","unstructured":"Hartmann, T.A., Jan\u00dfen, T.: Approximating $$\\delta $$-Covering (2024). https:\/\/arxiv.org\/abs\/2408.04517"},{"key":"5_CR12","doi-asserted-by":"publisher","unstructured":"Hartmann, T.A., Lendl, S.: Dispersing obnoxious facilities on graphs by rounding distances. In: Szeider, S., Ganian, R., Silva, A. (eds.) 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022. LIPIcs, 22\u201326 August 2022, Vienna, Austria, vol.\u00a0241, pp. 55:1\u201355:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2022.55","DOI":"10.4230\/LIPIcs.MFCS.2022.55"},{"issue":"1","key":"5_CR13","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10107-021-01646-x","volume":"192","author":"TA Hartmann","year":"2022","unstructured":"Hartmann, T.A., Lendl, S., Woeginger, G.J.: Continuous facility location on graphs. Math. Program. 192(1), 207\u2013227 (2022). https:\/\/doi.org\/10.1007\/s10107-021-01646-x","journal-title":"Math. Program."},{"key":"5_CR14","doi-asserted-by":"publisher","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. In: Aho, A.V., et al. (eds.) Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 30 April\u20132 May 1973, Austin, Texas, USA, pp. 38\u201349. ACM (1973). https:\/\/doi.org\/10.1145\/800125.804034","DOI":"10.1145\/800125.804034"},{"key":"5_CR15","doi-asserted-by":"publisher","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Reif, J.H. (ed.) Proceedings on 34th Annual ACM Symposium on Theory of Computing, 19\u201321 May 2002, Montr\u00e9al, Qu\u00e9bec, Canada, pp. 767\u2013775. ACM (2002). https:\/\/doi.org\/10.1145\/509907.510017","DOI":"10.1145\/509907.510017"},{"issue":"3","key":"5_CR16","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008). https:\/\/doi.org\/10.1016\/j.jcss.2007.06.019","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"5_CR17","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discret. Math. 13(4), 383\u2013390 (1975). https:\/\/doi.org\/10.1016\/0012-365X(75)90058-8","journal-title":"Discret. Math."},{"issue":"4","key":"5_CR18","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1137\/0212051","volume":"12","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N., Tamir, A.: New results on the complexity of p-center problems. SIAM J. Comput. 12(4), 751\u2013758 (1983). https:\/\/doi.org\/10.1137\/0212051","journal-title":"SIAM J. Comput."},{"key":"5_CR19","unstructured":"Mirchandani, P.B., Francis, R.L.: Discrete Location Theory (1990)"},{"key":"5_CR20","doi-asserted-by":"publisher","unstructured":"Tamir, A.: On the solution value of the continuous p-center location problem on a graph. Math. Oper. Res. 12(2), 340\u2013349 (1987). https:\/\/doi.org\/10.1287\/moor.12.2.340","DOI":"10.1287\/moor.12.2.340"},{"key":"5_CR21","doi-asserted-by":"publisher","unstructured":"Tamir, A.: Obnoxious facility location on graphs. SIAM J. Discret. Math. 4(4), 550\u2013567 (1991). https:\/\/doi.org\/10.1137\/0404048","DOI":"10.1137\/0404048"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-81396-2_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T21:14:18Z","timestamp":1739394858000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-81396-2_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031813955","9783031813962"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-81396-2_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"12 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Egham","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo-conference.org\/2024\/waoa\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}