Semidefinite Programming Relaxations Of Maximin Dispersion Problems

The maxmin dispersion problem is tolocate a point in a given set(an n-dimensional unit Euclidean ball)such that the minimum of the weighted Euclidean distance from m given points is maximized.The maxmin dispersion problem has many diverse applications infacility location,spatial management,and pattern recognition.One applied example in facility location would be determining of a location for a new and highly pollution garbage dump or chemical plant far from the crowd gathering are as such as schools or communities.In general,the weighted maxmin dispersion problem is neither convex nor concave.A new proof is provided for the existence of a semidefinite programming relaxation of an existed maxmin dispersion problem.This paper considers two new kinds of maxmin dispersion problems;the NP-hardness is showed for the box-constrained or the ball-constrained maxmin dispersion problem;new semidefinite programming relaxations are proposed for these mamin dispersion problem;the Gershgorin disc theorem is used to prove the existence of the semidefinite programming relaxation;a randomized approximation algorithm is designed for the box-constrained maxmin dispersion problem;a numerical experiment is also conducted for illustrating the feasibility of the randomized approximation algorithm.1.In Chaper 2,considered a box-constrained maxmin dispersion problem from references of Haines.A new proof is provided for the existence of a SDP relaxation of an existed maxmin dispersion problem by use the Gershgorin's disc theory.It provides a theoretical basis for Sedumi to solve this kind of semidefinite relaxation problem effectively.2.In Chaper 3,considered a new box-constrained maxmin dispersion problem,the NP-hardness is showed for the box-constrained maxmin dispersion problem,and the SDP relaxation problem is given.By use the Gershgorin's disc theory given a new proof for the existence of a SDP relaxation of an existed maxmin dispersion problem.A randomized approximation algorithm is designed for the box-constrained maxmin dispersion problem.a numerical experiment is also conducted for illustrating the feasibility of the randomized approximation algorithm.3.In Chaper 4,considered a new ball-constrained maxmin dispersion problem.The NP-hardness is showed for the ball-constrained maxmin dispersion problem,and the SDP relaxation problem is given.By use the Gershgorin's disc theory given a new proof for the existence of a SDP relaxation of an existed maxmin dispersion problem.4.In Chaper 5,also considered a new box-constrained maxmin dispersion problem.And the SDP relaxation problem is given.By use the Gershgorin's disc theory given a new proof for the existence of a SDP relaxation of an existed maxmin dispersion problem.