Article1991

Obnoxious Facility Location on Graphs

147 citations0/0 files storedSIAM Journal on Discrete Mathematics

No readable copy stored yet — this record is metadata only.

Facility Location and Emergency Management Complexity and Algorithms in Graphs Computational Geometry and Mesh Generation

Abstract

This paper discusses new complexity results for several models dealing with the location of obnoxious or undesirable facilities on graphs. The focus is mainly on the continuous p-Maximin and p-Maxisum dispersion models, where the facilities can be established at the nodes or in the interiors of the edges. For the general (nonhomogeneous) case it is shown that both models are strongly NP-hard even when the underlying graph consists of a single edge. For the homogeneous p-Maximin model it is proven that even the problem of finding a $\frac{2}{3}$-approximation solution is NP-hard, and a polynomial heuristic which provides a $\frac{1}{2}$-approximation to the model is presented. Tree graphs are considered, and new algorithms with lower complexity bounds for several versions of the model are presented. For the p-Maxisum problem we show that the homogeneous case is NP-hard on general graphs. Turning to the homogeneous case on trees, a certain concavity property is identified and then utilized to improve upon the best known methods to solve this model.

Citations in this library

Stored only when both papers are in the corpus — 147 citations exist upstream.

References

1989Analytical models for locating undesirable facilities 1991Discrete Location Theory 1990The discrete p-dispersion problem 1978Locating an Obnoxious Facility on a Network 1987Programming Models for Facility Dispersion: The p‐Dispersion and Maxisum Dispersion Problems 1984An Analysis of Network Location Problems with Distance Constraints 1985A simple heuristic for the p-centre problem

Cited by

2011Strategy-proof approximation mechanisms for an obnoxious facility game on networks 2013Public facility location using dispersion, population, and equity criteria 2006The minimum weighted covering location problem with distance constraints 2019Less is more approach: basic variable neighborhood search for the obnoxious p‐median problem 2024Fifty Years of Location Theory - A Selective Review 2016Advanced Greedy Randomized Adaptive Search Procedure for the Obnoxious p-Median problem 2006A branch-and-cut method for the obnoxious p-median problem

Imported from OpenAlex (CC0) — nothing here is generated.