文献类型：期刊文献

英文题名：A local search algorithm 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

卷号：18

期号：1

起止页码：279

外文期刊名：OPTIMIZATION LETTERS

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

基金：AcknowledgementsThe authors are grateful to the anonymous referees for their valuable and constructive comments. This research is supported by the National Natural Science Foundation of China under Grant Numbers 11671135, 11871213 and the Natural Science Foundation of Shanghai under Grant Number 19ZR1411800.

语种：英文

外文关键词：Approximation algorithm; Path partition; Set covering; Local search

摘要：Given an undirected graph G = (V, E), the k-path partition problem is to find a collection of vertex-disjoint paths containing at most k vertices to cover all the vertices of V. The objective is to minimize the number of paths in the collection. For the k-path partition problem with k >= 3 , we propose a simple local search algorithm, whose approximation ratio improves on the best-known approximation algorithm in Chen (in: Chen, Li, Zhang (eds) Frontiers of algorithmics, Springer, Cham, 2022) for every k >= 4 , especially for k = 4, 5, 6, 7 . In addition, we give examples to show that our algorithm is tight when k is odd. When k is even, we give almost tight examples.