Search

Given an undirected complete graph G = (V , E) with nonnegative edge weight function obeying the triangle inequality, a set { C 1 , C 2 , ... , C k } of cycles is called a cycle cover if V ⊆ ⋃ i = 1 k V (C i) , where V (C i) represents the set of vertices in C i , and its cost is given by the maximum weight of the cycles. The Minimum Cycle Cover Problem (MCCP) aims to find a cycle cover of cost at most λ with the minimum number of cycles. We propose new LP relaxations for MCCP as well as its variants, called the Minimum Path Cover Problem (MPCP) and the Minimum Tree Cover Problem, where the cycles are replaced by paths or trees. Moreover, we give new LP relaxations for a special case of the rooted version of MCCP/MPCP. We show that these LP relaxations have significantly better integrality gaps than the previous relaxations. [ABSTRACT FROM AUTHOR]

• The minimum cycle cover problem. • A simplified approach of analysis. • An O (n 2) time 24/5-approximation algorithm. • A new O (n 3) time 14/3-approximation algorithm. • An improved O (n 5) time 32/7-approximation algorithm. Given an undirected weighted graph G = (V , E) with nonnegative weight function obeying the triangle inequality, a set { C 1 , C 2 , ... , C k } of cycles is called a cycle cover if V ⊆ ⋃ i = 1 k V (C i) and its cost is given by the maximum weight of the cycles. The Minimum Cycle Cover Problem aims to find a cycle cover of cost at most λ with the minimum number of cycles. An O (n 2) 24/5-approximation algorithm and an O (n 5) 14/3-approximation algorithm are given by Yu and Liu (Improved approximation algorithms for some min-max cycle cover problems. Theoretical Computer Science 654 (2016) 45–58). However, the original proofs for approximation ratios are incomplete. In this paper we first present a corrected simplified analysis on the 24/5-approximation algorithm. Based on the simplified approach of analysis and some new observations, we present a new 14/3-approximation algorithm that runs in O (n 3) and give an improved 32/7-approximation algorithm that runs in O (n 5). [ABSTRACT FROM AUTHOR]

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]

In this paper, we investigate a semi-online scheduling problem on two uniform machines with the speed ratio s . It is assumed that all jobs have their processing times between p and tp ( p > 0 , t ≥ 1 ). The objective is to minimize the makespan. We give the competitive ratio of LS algorithm which is a piecewise function on t ≥ 1 and s ≥ 1 . It shows that LS is an optimal algorithm for most regions on s and t . We further present two optimal algorithms. The algorithm H 1 with competitive ratio of s is optimal for 1.325 ≤ s ≤ 1 + 5 2 and s < t ≤ s 2 − 1 1 + s − s 2 . The algorithm H 2 with competitive ratio of s is optimal for 1.206 ≤ s ≤ 1.5 and s ≤ t ≤ min ⁡ { 2 s − 1 , 2 ( s 2 − 1 ) 1 + s − s 2 } , and it is also optimal for 1 ≤ s ≤ 1 + 17 4 and max ⁡ { 2 s − 1 , − s + 9 s 2 + 8 s 2 s } ≤ t ≤ 2 s with competitive ratio of 1 + t 2 . [ABSTRACT FROM AUTHOR]