Document Open Access Logo

Dispersing Obnoxious Facilities on a Graph

Authors Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl, Gerhard J. Woeginger

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2019.33.pdf
  • Filesize: 448 kB
  • 11 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Discrete optimization
Keywords
  • algorithms
  • complexity
  • optimization
  • graph theory
  • facility location

Metrics

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

Abstract

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 delta from each other.
We investigate the complexity of this problem in terms of the rational parameter delta. The problem is polynomially solvable, if the numerator of delta is 1 or 2, while all other cases turn out to be NP-hard.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 33:1-33:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.33

Author Details

Alexander Grigoriev
  • Department of Quantitative Economics, Maastricht University, Maastricht, The Netherlands
Tim A. Hartmann
  • Department of Computer Science, RWTH Aachen, Aachen, Germany
Stefan Lendl
  • Institute of Discrete Mathematics, TU Graz, Graz Austria
Gerhard J. Woeginger
  • Department of Computer Science, RWTH Aachen, Aachen Germany

Funding

  • Lendl, Stefan: Supported by the Austrian Science Fund (FWF): W1230, Doctoral Program "Discrete Mathematics".
  • Woeginger, Gerhard J.: Supported by the DFG RTG 2236 "UnRAVeL".

Acknowledgements

The research in this paper has been started during the Lorentz Center Workshop on Fixed-Parameter Computational Geometry, which was organized in May 2018 in Leiden. We thank the Lorentz Center for its hospitality. Alexander Grigoriev and Gerhard Woeginger acknowledge helpful discussions with Fedor Fomin, Petr Golovach and Jesper Nederlof.

References

  1. S. Abravaya and M. Segal. Maximizing the number of obnoxious facilities to locate within a bounded region. Computers and Operations Research, 37:163-171, 2010. Google Scholar
  2. P. Cappanera. A survey on obnoxious facility location problems. Technical report, Dipartimento di Informatica, Universitá di Pisa, Italy, 2010. Google Scholar
  3. R.L. Church and R.S. Garfinkel. Locating an obnoxious facility on a network. Transportation Science, 12:107-118, 1978. Google Scholar
  4. W.R. Cunningham. On submodular function minimization. Combinatorica, 5:185-192, 1985. Google Scholar
  5. J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965. Google Scholar
  6. E. Erkut and S. Neuman. Analytical models for locating undesirable facilities. European Journal of Operational Research, 40:275-291, 1989. Google Scholar
  7. T. Gallai. Kritische Graphen II. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 8:373-395, 1963. Google Scholar
  8. T. Gallai. Maximale Systeme unabhängiger Kanten. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 9:401-413, 1964. Google Scholar
  9. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  10. A.J. Goldman and P.M. Dearing. Concepts of optimal location for partially noxious facilities. ORSA Bulletin, 23:B-31, 1975. Google Scholar
  11. M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer Verlag, 1988. Google Scholar
  12. L. Lovász and M.D. Plummer. Matching Theory. Annals of Discrete Mathematics 29, North-Holland, Amsterdam, 1986. Google Scholar
  13. N. Megiddo and A. Tamir. New results on the complexity of p-center problems. SIAM Journal on Computing, 12:751-758, 1983. Google Scholar
  14. M. Segal. Placing an obnoxious facility in geometric networks. Nordic Journal of Computing, 10:224-237, 2003. Google Scholar
  15. A. Tamir. Obnoxious facility location on graphs. SIAM Journal on Discrete Mathematics, 4:550-567, 1991. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact