{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:42Z","timestamp":1740109302221,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T00:00:00Z","timestamp":1614297600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T00:00:00Z","timestamp":1614297600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"DFG","award":["RTG 2236"],"award-info":[{"award-number":["RTG 2236"]}]},{"name":"FWF","award":["W1230"],"award-info":[{"award-number":["W1230"]}]},{"DOI":"10.13039\/501100007210","name":"RWTH Aachen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007210","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that any two facilities have at least distance <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b4<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> from each other. We investigate the complexity of this problem in terms of the rational parameter <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b4<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The problem is polynomially solvable, if the numerator of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b4<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is 1 or 2, while all other cases turn out to be NP-hard.<\/jats:p>","DOI":"10.1007\/s00453-021-00800-3","type":"journal-article","created":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T12:03:17Z","timestamp":1614340997000},"page":"1734-1749","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dispersing Obnoxious Facilities on a Graph"],"prefix":"10.1007","volume":"83","author":[{"given":"Alexander","family":"Grigoriev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim A.","family":"Hartmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Lendl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8816-2693","authenticated-orcid":false,"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,26]]},"reference":[{"key":"800_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.cor.2009.04.004","volume":"37","author":"S Abravaya","year":"2010","unstructured":"Abravaya, S., Segal, M.: Maximizing the number of obnoxious facilities to locate within a bounded region. Comput. Oper. Res. 37, 163\u2013171 (2010)","journal-title":"Comput. Oper. Res."},{"issue":"6","key":"800_CR2","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1142\/S0218195900000322","volume":"10","author":"Boaz Ben-Moshe","year":"2000","unstructured":"Ben-Moshe, Boaz, Katz, Matthew J., Segal, Michael: Obnoxious facility location: complete service with minimal harm. Int. J. Comput. Geom. Appl. 10(6), 581\u2013592 (2000)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"800_CR3","unstructured":"Cappanera, P.: A survey on obnoxious facility location problems. Technical report, Dipartimento di Informatica, Universit\u00e1 di Pisa, Italy (2010)"},{"key":"800_CR4","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1287\/trsc.12.2.107","volume":"12","author":"RL Church","year":"1978","unstructured":"Church, R.L., Garfinkel, R.S.: Locating an obnoxious facility on a network. Transp. Sci. 12, 107\u2013118 (1978)","journal-title":"Transp. Sci."},{"key":"800_CR5","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF02579361","volume":"5","author":"WR Cunningham","year":"1985","unstructured":"Cunningham, W.R.: On submodular function minimization. Combinatorica 5, 185\u2013192 (1985)","journal-title":"Combinatorica"},{"key":"800_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":"800_CR7","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0377-2217(89)90420-7","volume":"40","author":"E Erkut","year":"1989","unstructured":"Erkut, E., Neuman, S.: Analytical models for locating undesirable facilities. Eur. J. Oper. Res. 40, 275\u2013291 (1989)","journal-title":"Eur. J. Oper. Res."},{"key":"800_CR8","first-page":"373","volume":"8","author":"T Gallai","year":"1963","unstructured":"Gallai, T.: Kritische Graphen II. A Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00d6zlem\u00e9nyei 8, 373\u2013395 (1963)","journal-title":"A Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00d6zlem\u00e9nyei"},{"key":"800_CR9","first-page":"401","volume":"9","author":"T Gallai","year":"1964","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)","journal-title":"A Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei"},{"key":"800_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"800_CR11","first-page":"B-31","volume":"23","author":"AJ Goldman","year":"1975","unstructured":"Goldman, A.J., Dearing, P.M.: Concepts of optimal location for partially noxious facilities. ORSA Bull. 23, B-31 (1975)","journal-title":"ORSA Bull."},{"key":"800_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00d6tschel","year":"1988","unstructured":"Gr\u00d6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, New York (1988)"},{"key":"800_CR13","doi-asserted-by":"crossref","unstructured":"Hartmann, T.A., Lendl, S., Woeginger, G.J.: Continuous facility location on graphs. In: Proceedings of the 21st International Conference on Integer Programming and Combinatorial Optimization (IPCO 2020), volume 12125 of Lecture Notes in Computer Science, pp. 171\u2013181. Springer (2020)","DOI":"10.1007\/978-3-030-45771-6_14"},{"issue":"13","key":"800_CR14","doi-asserted-by":"publisher","first-page":"1859","DOI":"10.1016\/S0305-0548(01)00063-6","volume":"29","author":"MJ Katz","year":"2002","unstructured":"Katz, M.J., Kedem, K., Segal, M.: Improved algorithms for placing undesirable facilities. Comput. Oper. Res. 29(13), 1859\u20131872 (2002)","journal-title":"Comput. Oper. Res."},{"key":"800_CR15","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. Annals of Discrete Mathematics 29. North-Holland, Amsterdam (1986)"},{"key":"800_CR16","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, 751\u2013758 (1983)","journal-title":"SIAM J. Comput."},{"key":"800_CR17","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, New York (2003)"},{"key":"800_CR18","first-page":"224","volume":"10","author":"M Segal","year":"2003","unstructured":"Segal, M.: Placing an obnoxious facility in geometric networks. Nordic J. Comput. 10, 224\u2013237 (2003)","journal-title":"Nordic J. Comput."},{"key":"800_CR19","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1137\/0404048","volume":"4","author":"A Tamir","year":"1991","unstructured":"Tamir, A.: Obnoxious facility location on graphs. SIAM J. Discrete Math. 4, 550\u2013567 (1991)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00800-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00800-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00800-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T10:05:41Z","timestamp":1621937141000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00800-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,26]]},"references-count":19,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["800"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00800-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,2,26]]},"assertion":[{"value":"11 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}