论文标题
$ p $ - centdian和Converse Centdian问题的近似性结果
Approximability results for the $p$-centdian and the converse centdian problems
论文作者
论文摘要
Given an undirected graph $G=(V,E)$ with a nonnegative edge length function and an integer $p$, $0 < p < |V|$, the $p$-centdian problem is to find $p$ vertices (called the {\it centdian set}) of $V$ such that the {\it eccentricity} plus {\it median-distance} is minimized, in which the {\ it偏心}是所有顶点到其最近的{\ it centdian set}的最大（长度）距离，并且{\ it Median-Distance}是所有顶点到其最近的{\ IT centdian set}的总（长度）距离}。 {\ it偏心} plus {\ it中位数}称为{\ it centdian-Distance}。 $ p $ - 中心问题的目的是找到$ p $开放设施（服务器），该设施满足最小总距离（{\ it中位数距离}）和最大距离（{\ it in iT偏心}）的服务质量。如果我们交谈两个标准，则给出了{\ it Centdian-Distance}的界限，并且目标函数是最大程度地减少{\ it Centdian set}的基数，此问题称为Converse Centdian问题。在本文中，我们证明了$ p $ - 中心问题是NP的完整问题。然后，我们分别针对$ p $ - 中心问题和相反的Centdian问题设计了第一个非平凡的蛮力精确算法。最后，我们针对这两个问题设计了两种近似算法。
Given an undirected graph $G=(V,E)$ with a nonnegative edge length function and an integer $p$, $0 < p < |V|$, the $p$-centdian problem is to find $p$ vertices (called the {\it centdian set}) of $V$ such that the {\it eccentricity} plus {\it median-distance} is minimized, in which the {\it eccentricity} is the maximum (length) distance of all vertices to their nearest {\it centdian set} and the {\it median-distance} is the total (length) distance of all vertices to their nearest {\it centdian set}. The {\it eccentricity} plus {\it median-distance} is called the {\it centdian-distance}. The purpose of the $p$-centdian problem is to find $p$ open facilities (servers) which satisfy the quality-of-service of the minimum total distance ({\it median-distance}) and the maximum distance ({\it eccentricity}) to their service customers, simultaneously. If we converse the two criteria, that is given the bound of the {\it centdian-distance} and the objective function is to minimize the cardinality of the {\it centdian set}, this problem is called the converse centdian problem. In this paper, we prove the $p$-centdian problem is NP-Complete. Then we design the first non-trivial brute force exact algorithms for the $p$-centdian problem and the converse centdian problem, respectively. Finally, we design two approximation algorithms for both problems.
