Document Open Access Logo

Dispersing Obnoxious Facilities on Graphs by Rounding Distances

Authors Tim A. Hartmann , Stefan Lendl

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.55.pdf
  • Filesize: 0.78 MB
  • 14 pages

Document Identifiers

Author Details

Tim A. Hartmann
  • Department of Computer Science, RWTH Aachen University, Germany
Stefan Lendl
  • Department of Operations and Information Systems, University of Graz, Austria

Cite As Get BibTex

Tim A. Hartmann and Stefan Lendl. Dispersing Obnoxious Facilities on Graphs by Rounding Distances. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.55

Abstract

We continue the study of δ-dispersion, 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 every two facilities have distance at least δ from each other.
Our main technical contribution is an efficient procedure to "round-up" distance δ. It transforms a δ-dispersed set S into a δ^⋆-dispersed set S^⋆ of same size where distance δ^⋆ is a potentially slightly larger rational a/b with a numerator a upper bounded by the longest (not-induced) path in the input graph.
Based on this rounding procedure and connections to the distance-d independent set problem we derive a number of algorithmic results. When parameterized by treewidth, the problem is in XP. When parameterized by treedepth the problem is FPT and has a matching lower bound on its time complexity under ETH. Moreover, we can also settle the parameterized complexity with the solution size as parameter using our rounding technique: δ-Dispersion is FPT for every δ ≤ 2 and W[1]-hard for every δ > 2.
Further, we show that δ-dispersion is NP-complete for every fixed irrational distance δ, which was left open in a previous work.

Subject Classification

ACM Subject Classification
  • Theory of computation → Discrete optimization
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Problems, reductions and completeness
Keywords
  • facility location
  • parameterized complexity
  • packing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Shimon Abravaya and Michael Segal. Maximizing the number of obnoxious facilities to locate within a bounded region. Comput. Oper. Res., 37(1):163-171, 2010. URL: https://doi.org/10.1016/j.cor.2009.04.004.
  2. Boaz Ben-Moshe, Matthew J. Katz, and Michael Segal. Obnoxious facility location: complete service with minimal harm. International Journal of Computational Geometry and Applications, 10(6):581-592, 2000. Google Scholar
  3. Richard L. Church and Robert S. Garfinkel. Locating an obnoxious facility on a network. Transportation Science, 12:107-118, 1978. Google Scholar
  4. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  5. Hiroshi Eto, Fengrui Guo, and Eiji Miyano. Distance-d independent set problems for bipartite and chordal graphs. J. Comb. Optim., 27(1):88-99, 2014. URL: https://doi.org/10.1007/s10878-012-9594-4.
  6. Alan J. Goldman and Perino M. Dearing. Concepts of optimal location for partially noxious facilities. ORSA Bulletin, 23:B-31, 1975. Google Scholar
  7. Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. Dispersing obnoxious facilities on a graph. In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, pages 33:1-33:11, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.33.
  8. Alexander Grigoriev, Tim A Hartmann, Stefan Lendl, and Gerhard J Woeginger. Dispersing obnoxious facilities on a graph. Algorithmica, 83(6):1734-1749, 2021. Google Scholar
  9. Tim A. Hartmann and Stefan Lendl. Dispersing obnoxious facilities on graphs by rounding distances, 2022. URL: https://doi.org/10.48550/ARXIV.2206.11337.
  10. Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. Continuous facility location on graphs. Math. Program., 192(1):207-227, 2022. URL: https://doi.org/10.1007/s10107-021-01646-x.
  11. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  12. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structurally parameterized d-scattered set. In Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, pages 292-305, 2018. URL: https://doi.org/10.1007/978-3-030-00256-5_24.
  13. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structurally parameterized d-scattered set. Discret. Appl. Math., 308:168-186, 2022. URL: https://doi.org/10.1016/j.dam.2020.03.052.
  14. Matthew J. Katz, Klara Kedem, and Michael Segal. Improved algorithms for placing undesirable facilities. Comput. Oper. Res., 29(13):1859-1872, 2002. URL: https://doi.org/10.1016/S0305-0548(01)00063-6.
  15. Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 931-942, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_77.
  16. Michael Segal. Placing an obnoxious facility in geometric networks. Nordic Journal of Computing, 10:224-237, 2003. Google Scholar
  17. Arie Tamir. On the solution value of the continuous p-center location problem on a graph. Math. Oper. Res., 12(2):340-349, 1987. URL: https://doi.org/10.1287/moor.12.2.340.
  18. Arie Tamir. Obnoxious facility location on graphs. SIAM J. Discret. Math., 4(4):550-567, 1991. URL: https://doi.org/10.1137/0404048.
  19. Martijn van Ee. Approximability of the dispersed p→-neighbor k-supplier problem. Discret. Appl. Math., 289:219-229, 2021. URL: https://doi.org/10.1016/j.dam.2020.10.007.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact