双会议服务器选址问题研究

Double Conference Servers Location Problem

中位选址问题一直是管理学科的研究热点,本文考虑平面点集选址问题中的双会议服务器选址问题,该问题可以看成是2中位问题的衍生问题。令P为平面上包含n个点的点集,双会议服务器选址问题即为寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并证明所给算法时间复杂性为O(n^(3)log n)。

The median location problem is always a hot issue in management science.In this paper,we consider the double conference servers location problem.Let P be a set of n points in the plane.The double conference servers location problem is to find a dipolar spanning tree spans P and minimize the sum of the distance among all pairs of leaves on this tree.In this paper,we show the key geometry structure and propose the exact algorithm which solves this problem in time.