论文标题
通过长路径覆盖顶点的近似算法
Approximation algorithms for covering vertices by long paths
论文作者
论文摘要
鉴于图形，总体上的问题是通过一系列顶点 - 偶像路径的集合来覆盖最大数量的顶点，看似从文献中逃脱了。一条至少包含$ k $顶点的路径被认为是长的。当$ k \ le 3 $时，问题是可以解决多项式时间；当$ k $是顶点的总数时，该问题将减少到Hamiltonian Path问题，这是NP完整的。对于固定的$ k \ ge 4 $，问题是NP-HARD，是加权设置包装问题的最著名的近似算法，意味着$ K $ - APPROXIMATION算法。据我们所知，没有直接为一般问题设计的近似算法。当$ k = 4 $时，该问题承认了最近提出的4美元 - 附件算法。我们提出了第一个$（0.4394 k + o（1））$ - 近似算法的一般问题，当$ k = 4 $时，提出了一般问题的近似算法，并提出了改进的$ 2 $ - APPRXIMATION ALGORITHM。两种算法均基于局部改进，其理论性能分析是通过摊销进行的，并通过仿真研究来检查其实际性能。
Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seemingly escapes from the literature. A path containing at least $k$ vertices is considered long. When $k \le 3$, the problem is polynomial time solvable; when $k$ is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed $k \ge 4$, the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a $k$-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when $k = 4$, the problem admits a $4$-approximation algorithm which was presented recently. We propose the first $(0.4394 k + O(1))$-approximation algorithm for the general problem and an improved $2$-approximation algorithm when $k = 4$. Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies.
