论文标题
对于哈密顿P-Median问题的特定情况
A 3-Approximation Algorithm for a Particular Case of the Hamiltonian p-Median Problem
论文作者
论文摘要
给定加权图$ g $带有$ n $顶点和$ m $边缘，以及一个正整数$ p $，汉密尔顿$ p $ -Median问题包括查找$ p $ p $ p $最低总重量，使每个顶点$ g $的每个顶点恰好是一个周期。我们引入了$ o（n^6）$ 3- approximation算法，其中$ p \ leq \ lceil \ frac \ frac {n-2 \ lceil \ frac {n} {5} {5} \ rceil} {3} {3} \ rceil $。根据$ g $的最佳2因子中的组件数量，可能会获得2个近似值。我们提出了将近似算法与文献的精确算法进行比较的计算实验。实际上，获得了更好的比率。对于$ p $的大值，确切的算法的表现优于我们的近似算法。
Given a weighted graph $G$ with $n$ vertices and $m$ edges, and a positive integer $p$, the Hamiltonian $p$-median problem consists in finding $p$ cycles of minimum total weight such that each vertex of $G$ is in exactly one cycle. We introduce an $O(n^6)$ 3-approximation algorithm for the particular case in which $p \leq \lceil \frac{n-2\lceil \frac{n}{5} \rceil}{3} \rceil$. An approximation ratio of 2 might be obtained depending on the number of components in the optimal 2-factor of $G$. We present computational experiments comparing the approximation algorithm to an exact algorithm from the literature. In practice much better ratios are obtained. For large values of $p$, the exact algorithm is outperformed by our approximation algorithm.
