کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475288 | 699275 | 2010 | 9 صفحه PDF | دانلود رایگان |
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∞L∞-distance as well as the L∞L∞-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 12-approximation algorithm for the problem, and employ the optimization algorithm to design a PTAS based on the shifting strategy [Hochbaum DS, Maass W. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM 1985;32:130–6]. As a byproduct we improve the algorithm for placing obnoxious facilities given by Katz et al. [Improved algorithms for placing undesirable facilities. Computers & Operations Research 2002;29:1859–72.].
Journal: Computers & Operations Research - Volume 37, Issue 1, January 2010, Pages 163–171