2023/11/19 by Jingyang Zhao, Zhao, Jingyang, Mingyu Xiao +1
Engineering · #Optimization and Packing Problems #graph theory and CDMA systems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2311.11332
Given an edge-weighted (metric/general) complete graph with n vertices, the maximum weight (metric/general) k-cycle/path packing problem is to find a set of (n)/(k) vertex-disjoint k-cycles/paths such that the total weight is maximized. In this paper, we consider approximation algorithms. For metric k-cycle packing, we improve the previous approximation ratio from 3/5 to 7/10 for k=5, and from 7/8⋅(1-1/k)2 for k>5 to (7/8-0.125/k)(1-1/k) for constant odd k>5 and to 7/8⋅ (1-1/k+(1)/(k(k-1))) for even k>5. For metric k-path packing, we improve the approximation ratio from 7/8⋅ (1-1/k) to (27k2-48k+16)/(32k2-36k-24) for even 10≥ k≥ 6. For the case of k=4, we improve the approximation ratio from 3/4 to 5/6 for metric 4-cycle packing, from 2/3 to 3/4 for general 4-cycle packing, and from 3/4 to 14/17 for metric 4-path packing.