.png){kind=icon}
.png){kind=icon}
Return
Approximation algorithms for the minimum weight cycle/path partition problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10878-026-01422-7.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Let G = (V, E) be an undirected complete graph on kn vertices. Each edge is associated with a non-negative weight. The edge weights satisfy the triangle inequality. A k-cycle partition is a set of n vertex-disjoint k-cycles, i.e. cycles containing exactly k vertices. The minimum weight k-cycle partition problem (MinWkCP) is to determine a k-cycle partition with minimum total edge weight. In the MinWkCP, if we replace cycles with paths, we obtain the minimum weight k-path partition problem (MinWkPP). 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 (1995). Then we deal with a special case of the MinWkCP and MinWkPP, where the edge weights are either 1 or 2, and propose approximation algorithms with ratios 8k(2)+14k-8/7k(2) and 8(k+1)/7k , respectively. For the MinW3PP and MinW3CP defined on {1, 2}-edge-weighted graphs, we develop two matching based algorithms with tight approximation ratios 3/2 and 5/3, respectively. Finally, for the {1, 2}-edge-weighted MinW3CP, we design a local search algorithm to further improve the ratio to 23/15 .
Keywords:
Approximation Algorithm
Cycle Partition
Path Partition
Matching
Local Search
Journal
J
IF:
1.1
Papers:
78
Citations:
0