LIPIcs.STACS.2019.33.pdf
- Filesize: 448 kB
- 11 pages
Document
Dispersing Obnoxious Facilities on a Graph
Authors
-
Part of:
Volume:
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-03-12
File
Document Identifiers
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.
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
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.
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)
0PDF Downloads
References
-
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.
-
P. Cappanera. A survey on obnoxious facility location problems. Technical report, Dipartimento di Informatica, Universitá di Pisa, Italy, 2010.
-
R.L. Church and R.S. Garfinkel. Locating an obnoxious facility on a network. Transportation Science, 12:107-118, 1978.
-
W.R. Cunningham. On submodular function minimization. Combinatorica, 5:185-192, 1985.
-
J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965.
-
E. Erkut and S. Neuman. Analytical models for locating undesirable facilities. European Journal of Operational Research, 40:275-291, 1989.
-
T. Gallai. Kritische Graphen II. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 8:373-395, 1963.
-
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.
-
M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
-
A.J. Goldman and P.M. Dearing. Concepts of optimal location for partially noxious facilities. ORSA Bulletin, 23:B-31, 1975.
-
M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer Verlag, 1988.
-
L. Lovász and M.D. Plummer. Matching Theory. Annals of Discrete Mathematics 29, North-Holland, Amsterdam, 1986.
-
N. Megiddo and A. Tamir. New results on the complexity of p-center problems. SIAM Journal on Computing, 12:751-758, 1983.
-
M. Segal. Placing an obnoxious facility in geometric networks. Nordic Journal of Computing, 10:224-237, 2003.
-
A. Tamir. Obnoxious facility location on graphs. SIAM Journal on Discrete Mathematics, 4:550-567, 1991.