TY - GEN
T1 - On some optimization problems in obnoxious facility location
AU - Qin, Zhongping
AU - Xu, Yinfeng
AU - Zhu, Binhai
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - In this paper we study the following general MaxMinoptimization problem concerning undesirable (obnoxious) facility location: Given a set of n sites S inside a convex region P, construct m garbage deposit sites Vm such that the minimum distance between these sites Vm and the union of S and Vm, Vm∪ S, is maximized. We present a general method using Voronoi diagrams to approximately solve two such problems when the sites S’s are points and weighted convex polygons (correspondingly, Vm‘s are points and weighted points and the distances are L2 and weighted respectively). In the latter case we generalize the Voronoi diagrams for disjoint weighted convex polygons in the plane. Our algorithms run in polynomial time and approximate the optimal solutions of the above two problems by a factor of 2.
AB - In this paper we study the following general MaxMinoptimization problem concerning undesirable (obnoxious) facility location: Given a set of n sites S inside a convex region P, construct m garbage deposit sites Vm such that the minimum distance between these sites Vm and the union of S and Vm, Vm∪ S, is maximized. We present a general method using Voronoi diagrams to approximately solve two such problems when the sites S’s are points and weighted convex polygons (correspondingly, Vm‘s are points and weighted points and the distances are L2 and weighted respectively). In the latter case we generalize the Voronoi diagrams for disjoint weighted convex polygons in the plane. Our algorithms run in polynomial time and approximate the optimal solutions of the above two problems by a factor of 2.
UR - https://www.scopus.com/pages/publications/84957007809
U2 - 10.1007/3-540-44968-x_32
DO - 10.1007/3-540-44968-x_32
M3 - 会议稿件
AN - SCOPUS:84957007809
SN - 3540677879
SN - 9783540677871
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 320
EP - 329
BT - Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings
A2 - Du, Ding-Zhu
A2 - Eades, Peter
A2 - Estivill-Castro, Vladimir
A2 - Lin, Xuemin
A2 - Sharma, Arun
PB - Springer Verlag
T2 - 6th Annual International Conference on Computing and Combinatorics, COCOON 2000
Y2 - 26 July 2000 through 28 July 2000
ER -