文献类型：期刊文献

英文题名：Approximation Algorithms for the Maximum-Weight Cycle/Path Packing Problems

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

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

年份：2023

卷号：40

期号：04

外文期刊名：ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH

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

基金：The 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; cycle packing; path packing; triangle inequality

摘要：Given an undirected complete graph G = (V, E) on kn vertices with a non-negative weight function on E, the maximum-weight k-cycle (k-path) packing problem aims to compute a set of n vertex-disjoint cycles (paths) in G containing k vertices so that the total weight of the edges in these n cycles (paths) is maximized. For the maximum-weight k-cycle packing problem, we develop an algorithm achieving an approximation ratio of alpha . (k-1/k)(2), where alpha is the approximation ratio for the maximum traveling salesman problem. For the case k = 4, we design a better 2/3-approximation algorithm. When the weights of edges obey the triangle inequality, we propose a 3/4-approximation algorithm and a 3/5-approximation algorithm for the maximum-weight k-cycle packing problem with k = 4 and k = 5, respectively. For the maximum-weight k-path packing problem with k = 3 (or k = 5) with the triangle inequality, we devise an algorithm with approximation ratio 3/4 and give a tight example.