文献类型：期刊文献

英文题名：Improved approximation algorithms for the k-path partition problem

作者：Li, Shiming[1];Yu, Wei[1];Liu, Zhaohui[1]

机构：[1]East China Univ Sci & Technol, Sch Math, 130 Meilong Rd, Shanghai 200237, Peoples R China

年份：2024

卷号：90

期号：4

起止页码：983

外文期刊名：JOURNAL OF GLOBAL OPTIMIZATION

收录：;EI(收录号：20243817046762);WOS:【SCI-EXPANDED(收录号:WOS:001317112100001)】；

基金：We are very grateful to the anonymous reviewers for their valuable comments and suggestions. This research is supported by the National Natural Science Foundation of China under grant number 12371317.

语种：英文

外文关键词：Approximation algorithm; Path partition problem; Maximum traveling salesman problem; Local search

摘要：The k-path partition problem (kPP), defined on a graph G =(V,E), is a well-known NP-hard problem whenk >= 3. The goal of the kPP is to find a minimum collection of vertex-disjoint paths to cover all the vertices in G such that the number of vertices on each path is no morethank. In this paper, we give two approximation algorithms for the kPP. The first one, called Algorithm 1, uses an algorithm for the (0,1)-weighted maximum traveling salesman problem as a subroutine. When G is undirected, the approximation ratio of Algorithm 1 isk+127-67k, which improves on the previous best-known approximation algorithm for everyk >= 7. WhenGis directed, Algorithm 1 is a(k+64-34k)-approximation algorithm, which improves the existing best available approximation algorithm for everyk >= 10. Our second algorithm, i.e. Algorithm 2, is a local search algorithm tailored for the kPP in undirected graphs with small k. Algorithm 2 improves on the approximation ratios of the best available algorithm foreveryk=4,5,6. Combined with Algorithms 1 and 2, we have improved the approximation ratio for the kPP in undirected graphs for eachk >= 4 as well as the approximation ratio fo the kPP in directed graphs for eachk >= 10. As for the negative side, we show that for any>0 it is NP-hard to approximate the kPP (with k being part of the input) within the ratio O (k(1-epsilon)), which implies that Algorithm 1 is asymptotically optimal.