文献类型：期刊文献

英文题名：Approximation Algorithms fortheMinimum Weight Cycle/Path Partition Problem

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

机构：[1] School of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

年份：2024

卷号：15179 LNCS

起止页码：170

外文期刊名：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

收录：EI(收录号：20244017144689)

语种：英文

外文关键词：Approximation algorithms - Graph algorithms - Graphic methods - Local search (optimization) - Undirected graphs

摘要：Let G=(V,E) be an undirected complete graph on kn vertices. Each edge is associated with a non-negative weight. The edge weights satisfies the triangle inequality. A k-cycle partitioning is a set of n vertex-disjoint k-cycles, i.e. cycles containing exactly k vertices (and thus k-1 edges). The minimum weight k-cycle partition problem (MinWkCP) aims to compute a k-cycle partition with minimum total edge weight. The minimum weight k-path partition problem (MinWkPP) is obtained by replacing cycles with paths in the MinWkCP. In this paper, we first devise a tight 32-approximation algorithm for the MinW4CP, improving on the best-known 3-approximation algorithm by Goemans and Williamson. Then we deal with a special case of the MinWkCP and MinWkPP, where the edge weights are either 1 or 2, and devise approximation algorithms with ratios 8k2+14k-87k2 and 8(k+1)7k, respectively. For the MinW3PP and MinW3CP on {1,2}-edge-weighted graphs, we propose two matching based algorithms with tight approximation ratios 32 and 53, respectively. Finally, for the {1,2}-edge-weighted MinW3CP, we design a local search algorithm to further improve the ratio to 85. ? The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.