.png){kind=icon}
返回
An Improved Approximation Algorithm for the Minimum k-Star Partition Problem
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0215-8_7.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
给定无向图 \( G = (V, E) \)，最小 \( k \)-星划分问题是要找到一个包含至多 \( k \) 个顶点的顶点不相交的星集合来覆盖 \( V \) 的所有顶点。目标是最小化集合中的星数量。在本文中，我们给出一个局部搜索算法，当 \( k \geq 5 \) 为偶数时，其近似比为 \( \frac{k}{2} - \frac{k-2}{k(k+1)} \)，当 \( k \geq 5 \) 为奇数时，近似比为 \( \frac{k}{2} - \frac{(k-2)}{(2k)^2} \)。这改进了由 Hell 和 Kirkpatrick 隐含的对于每个 \( k \geq 5 \) 的 \( \frac{k}{2} \) 近似算法。此外，我们给出了例子来证明我们的分析是紧的。
Keyword:
Approximation Algorithm
Star Partition
Path Partition
Local Search
期刊
C
IF:
0
论文数:
24
被引数:
0
.png){kind=icon}
查看更多内容