A strongly polynomial time approximation algorithm for the min-max clustered cycle cover problem

We reconsider the min-max clustered cycle cover (MM-CCC) problem, which is described as follows. Given an undirected complete graph G = ( V , E ; w ) with a positive integer k , where the vertex set V is partitioned into h clusters V 1 , … , V h , and w : E → R + is an edge-weight function satisfying the triangle inequality, it is asked to find k cycles such that they traverse all vertices and the vertices in each cluster are required to be traversed consecutively. The objective is to minimize the weight of the maximum weight cycle. We propose a strongly polynomial time 16-approximation algorithm for the MM-CCC problem. The result improves the previous algorithm in terms of running time.