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 consider the scheduling problem in which the jobs are first processed on a single machine and then delivered in batches by a single vehicle with limited capacity to the respective customers located at the vertices of a star-shaped network. The goal is to minimize the makespan. We present a 3/2-approximation algorithm for the identical job size case and a 2-approximation algorithm for the non-identical job sizes case. [ABSTRACT FROM AUTHOR]

Abstract: We consider the single vehicle scheduling problem in which the customers are located at the vertices of a tree or a cycle, and have release and service time requirements. The objective is to minimize the makespan. In the tour-version the makespan means the time when the vehicle returns to its initial location after serving all customers. While in the path-version the makespan refers to the maximum completion time of all customers. For the problem on a tree, we present a -approximation algorithm for the tour-version and a -approximation algorithm for the path-version. For the problem on a cycle, we present -approximation algorithms for both versions. [Copyright &y& Elsevier]

In this work we introduce the Minimum Rural Postmen Cover Problem (MRPCP) and the Minimum Chinese Postmen Cover Problem (MCPCP). The MRPCP aims to cover a given subset R of edges of an undirected weighted graph G = (V , E) by a minimum size set of closed walks of bounded length λ. The MCPCP is a special case of the MRPCP with R = E. We give the first approximation algorithms for these two problems, which have constant approximation ratios of 5 and 4, respectively. [ABSTRACT FROM AUTHOR]

In this paper, we study a multiple-terminal extension of the classic Hamiltonian path problem where m salesmen are initially located at different depots and finally stopped at different terminals. To the best of our knowledge, only 2-approximation algorithm is available in the literature. For arbitrary m ⩾ 2 , we first present a Christofides-like heuristic with a tight approximation ratio of 2 − 1 2 m + 1 . Besides, we also develop a (5 3 + ϵ) -approximation algorithm by divide-and-conquer technique. The (5 3 + ϵ) -approximation algorithm runs in polynomial time for fixed m and ϵ. [ABSTRACT FROM AUTHOR]