Dispersing obnoxious facilities on a graph

Alexander Grigoriev; Tim A.  Hartmann; Stefan  Lendl; Gerhard J. Woeginger

Dispersing obnoxious facilities on a graph

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

Data Analytics and Digitalisation

Research output: Book/Report › Report › Academic

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

Original language	English
Place of Publication	Cornell University Library, US
Publisher	Cornell University - arXiv
Number of pages	13
Volume	1811.08918
Publication status	Published - 21 Nov 2018

Publication series

Series	cs.DS

JEL classifications

c00 - Mathematical and Quantitative Methods: General

Keywords

Algorithms
Complexity
Optimization
Graph theory
Facility location

Access to Document

https://arxiv.org/abs/1811.08918

Cite this

@book{b55d63584b1840909f9b7de6f3957c77,

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

keywords = "Algorithms, Complexity, Optimization, Graph theory, Facility location",

author = "Alexander Grigoriev and Hartmann, {Tim A.} and Stefan Lendl and Woeginger, {Gerhard J.}",

note = "data source: NO DATA USED",

year = "2018",

month = nov,

day = "21",

language = "English",

volume = "1811.08918",

series = "cs.DS",

publisher = "Cornell University - arXiv",

address = "United States",

}

TY - BOOK

T1 - Dispersing obnoxious facilities on a graph

AU - Grigoriev, Alexander

AU - Hartmann, Tim A.

AU - Lendl, Stefan

AU - Woeginger, Gerhard J.

N1 - data source: NO DATA USED

PY - 2018/11/21

Y1 - 2018/11/21

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

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

KW - Algorithms

KW - Complexity

KW - Optimization

KW - Graph theory

KW - Facility location

M3 - Report

VL - 1811.08918

T3 - cs.DS

BT - Dispersing obnoxious facilities on a graph

PB - Cornell University - arXiv

CY - Cornell University Library, US

ER -