Back to Search
Start Over
Improved approximation algorithms for some min-max and minimum cycle cover problems.
- Source :
-
Theoretical Computer Science . Nov2016, Vol. 654, p45-58. 14p. - Publication Year :
- 2016
-
Abstract
- Given an undirected weighted graph G = ( V , E ) , a set { C 1 , C 2 , … , C k } of cycles is called a cycle cover of the vertex subset V ′ if V ′ ⊆ ∪ i = 1 k V ( C i ) and its cost is given by the maximum weight of the cycles. The Min-Max Cycle Cover Problem (MMCCP) is to find a minimum cost cycle cover of V with at most k cycles. The Rooted Min-Max Cycle Cover Problem (RMMCCP) is to find a minimum cost cycle cover of V ∖ D with at most k cycles, each of which contains one vertex in D . The Minimum Cycle Cover Problem (MCCP) aims to find a cycle cover of V of cost at most λ with the minimum number of cycles. We propose approximation algorithms for MMCCP and RMMCCP with performance ratios 5 and 6, respectively. These results improve the previous algorithms in term of both approximation ratios and running times. For MCCP we obtain a 14 3 -approximation algorithm that has the same time complexity as the previous best 5-approximation algorithm. Moreover, we transform a ρ -approximation algorithm for TSP into approximation algorithms for MMCCP, RMMCCP and MCCP with ratios 4 ρ , 4 ρ + 1 and 4 ρ , respectively. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 654
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 119651970
- Full Text :
- https://doi.org/10.1016/j.tcs.2016.01.041