{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:47Z","timestamp":1740109307052,"version":"3.37.3"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/rtg","name":"DFG","doi-asserted-by":"publisher","id":[{"id":"10.13039\/rtg","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["W1230"],"award-info":[{"award-number":["W1230"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study a continuous facility location problem on undirected graphs where all edges have unit length and where the facilities may be positioned on the vertices as well as on interior points of the edges. The goal is to cover the entire graph with a minimum number of facilities with covering range <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta &gt;0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In other words, we want to position as few facilities as possible subject to the condition that every point on every edge is at distance at most <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 one of these facilities. We investigate this covering 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>. We prove that the problem is polynomially solvable whenever <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 a unit fraction, and that the problem is NP-hard for all non unit fractions <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>. We also analyze the parametrized complexity with the solution size as parameter: The resulting problem is fixed parameter tractable for <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta &lt;3\/2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and it is <jats:italic>W<\/jats:italic>[2]-hard for <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta \\ge 3\/2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s10107-021-01646-x","type":"journal-article","created":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T16:02:58Z","timestamp":1616774578000},"page":"207-227","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Continuous facility location on graphs"],"prefix":"10.1007","volume":"192","author":[{"given":"Tim A.","family":"Hartmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Lendl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,26]]},"reference":[{"key":"1646_CR1","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24, 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"key":"1646_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(97)00101-1","volume":"209","author":"RG Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R.: Threshold dominating sets and an improved characterization of $$W[2]$$. Theoret. Comput. Sci. 209, 123\u2013140 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"1646_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, Berlin (1999)"},{"key":"1646_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5355-6","volume-title":"Facility Location: a Survey of applications and methods. Springer Series in operations research","author":"Z Drezner","year":"1995","unstructured":"Drezner, Z.: Facility Location: a Survey of applications and methods. Springer Series in operations research. Springer, New York (1995)"},{"key":"1646_CR5","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":"1646_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1287\/opre.1040.0137","volume":"53","author":"SP Fekete","year":"2005","unstructured":"Fekete, S.P., Mitchell, J.S.B., Beurer, K.: On the continuous Fermat-Weber problem. Oper. Res. 53, 61\u201376 (2005)","journal-title":"Oper. Res."},{"key":"1646_CR7","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\u00f6zlem\u00e9nyei 8, 373\u2013395 (1963)","journal-title":"A Magyar Tudom\u00e1nyos Akad\u00e9mia Matematikai Kutat\u00f3 Int\u00e9zet\u00e9nek K\u00f6zlem\u00e9nyei"},{"key":"1646_CR8","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"},{"unstructured":"Grigoriev, A., Hartmann, T.A., Lendl, S., Woeginger, G.J.: Dispersing obnoxious facilities on a graph. Proceedings of the 36th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u20192019), Leibniz International Proceedings in Informatics, LIPICS 126, 33:1\u201333:11 (2019)","key":"1646_CR9"},{"key":"1646_CR10","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0137040","volume":"37","author":"O Kariv","year":"1979","unstructured":"Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems, Part I. The $$p$$-centers. SIAM J. Appl Math 37, 513\u2013538 (1979)","journal-title":"SIAM J. Appl Math"},{"key":"1646_CR11","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":"1646_CR12","volume-title":"Discrete Location Theory","author":"PB Mirchandani","year":"1990","unstructured":"Mirchandani, P.B., Francis, R.L.: Discrete Location Theory. Wiley, New York (1990)"},{"key":"1646_CR13","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":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01646-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01646-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01646-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T17:18:14Z","timestamp":1646846294000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01646-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,26]]},"references-count":13,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1646"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01646-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,3,26]]},"assertion":[{"value":"29 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}