Maximizing the number of obnoxious facilities to locate within a bounded region. (English) Zbl 1171.90455

Summary: This paper deals with the problem of locating a maximal cardinality set of obnoxious facilities within a bounded rectangle in the plane such that their pairwise \(L_{\infty }\)-distance as well as the \(L_{\infty }\)-distance to a set of already placed demand sites is above a given threshold. We employ techniques and methods from computational geometry to design an optimization algorithm and an efficient \(\frac 1 2\)-approximation algorithm for the problem, and employ the optimization algorithm to design a PTAS based on the shifting strategy [D. S. Hochbaum and W. Maass, J. Assoc. Comput. Mach. 32, 130–136 (1985; Zbl 0633.68027)]. As a byproduct we improve the algorithm for placing obnoxious facilities given by M. Katz et al. [Improved algorithms for placing undesirable facilities. ibid. 29, 1859–72 (2002)].


90B85 Continuous location


Zbl 0633.68027
Full Text: DOI


[1] Baur, C.; Fekete, S.P., Approximation of geometric dispersion problems, Algorithmica, 30, 451-470, (2001) · Zbl 0986.65010
[2] Benkert, M.; Gudmundsson, J.; Knauer, C.; Moet, E.; van Oostrum, R.; Wolff, A., A polynomial-time approximation algorithm for a geometric dispersion problem, (), 141-144
[3] Ben-Moshe, B.; Katz, M.J.; Segal, M., Obnoxious facility location: complete service with minimal harm, International journal of computational geometry & applications, 10, 581-592, (2000) · Zbl 0970.68178
[4] Brimberg, J.; Mehrez, A., Multi-facility location using a maximin criterion and rectangular distances, Location science, 2, 11-19, (1994) · Zbl 0929.90045
[5] Cappanera P. A survey on obnoxious facility location problems. Technical Report, 1999.
[6] Fowler, R.J.; Paterson, M.S.; Tanimoto, S.L., Optimal packing and covering in the plane are NP-complete, Information processing letters, 12, 133-137, (1981) · Zbl 0469.68053
[7] Hochbaum, D.S.; Maass, W., Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM, 32, 130-136, (1985) · Zbl 0633.68027
[8] Huang, H.; Richa, A.W.; Segal, M., Dynamic coverage in ad hoc sensor networks, Mobile networks & applications, 10, 9-17, (2005)
[9] Katz, M.; Kedem, K.; Segal, M., Improved algorithms for placing undesirable facilities, Computers & operations research, 29, 1859-1872, (2002) · Zbl 1259.90060
[10] Lorenzetti, M.; Preas, B., Physical design automation of VLSI systems, (1988), Benjamin/Cummings Publishing Company California
[11] Mehlhorn, K.; Näher, S., Dynamic fractional cascading, (), 215-241 · Zbl 0693.68038
[12] Plastria, F., Continuous covering location problems, (), 39-83
[13] Preparata, F.P.; Shamos, M.I., Computational geometry: an introduction, (1985), Springer NY · Zbl 0759.68037
[14] Qin, Z.; Xu, Y.; Zhu, B., On some optimization problems in obnoxious facility location, () · Zbl 1039.90037
[15] Tamir, A., Locating two obnoxious facilities using the weighted maximin criterion, Operations research letters, 34, 97-105, (2006) · Zbl 1080.90053
[16] Welch SB, Salhi S, Drezner Z. The multifacility maximin planar location problem with facility interaction. IMA Journal of Management Mathematics 2006;1-16. · Zbl 1126.90048
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.