License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.33
URN: urn:nbn:de:0030-drops-102729
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10272/
Grigoriev, Alexander ;
Hartmann, Tim A. ;
Lendl, Stefan ;
Woeginger, Gerhard J.
Dispersing Obnoxious Facilities on a Graph
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.
BibTeX - Entry
@InProceedings{grigoriev_et_al:LIPIcs:2019:10272,
author = {Alexander Grigoriev and Tim A. Hartmann and Stefan Lendl and Gerhard J. Woeginger},
title = {{Dispersing Obnoxious Facilities on a Graph}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {33:1--33:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-100-9},
ISSN = {1868-8969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10272},
doi = {10.4230/LIPIcs.STACS.2019.33},
annote = {Keywords: algorithms, complexity, optimization, graph theory, facility location}
}
|
Keywords: |
|
algorithms, complexity, optimization, graph theory, facility location |
|
Collection: |
|
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
12.03.2019 |
