Approximation Algorithms for the Maximum-Weight Cycle/Path Packing Problems

Shiming Li () and Wei Yu
Additional contact information
Shiming Li: School of Mathematics, East China University of Science and Technology, Shanghai 200237, P. R. China
Wei Yu: School of Mathematics, East China University of Science and Technology, Shanghai 200237, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 04, 1-16

Abstract: 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 α ⋅ (k−1 k )2, where α 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.

Keywords: Approximation algorithm; cycle packing; path packing; triangle inequality (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595923400031
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:40:y:2023:i:04:n:s0217595923400031

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595923400031

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().