Approximation algorithms for two clustered arc routing problems.

Given a strongly connected mixed graph G = (V , E , A) , where V represents the vertex set, E is the undirected edge set, and A is the directed arc set, R ⊆ E is a subset of required edges and is divided into p clusters R 1 , R 2 , ⋯ , R p , and A is a set of required arcs and is partitioned into q clusters A 1 , A 2 , … , A q . Each edge in E and each arc in A are associated with a nonnegative weight and the weight function satisfies the triangle inequality. In this paper we consider two clustered arc routing problems. The first is the Clustered Rural Postman Problem, in which A is empty and the objective is to find a minimum-weight closed walk such that all the edges in R are serviced and the edges in R i ( 1 ≤ i ≤ p ) are serviced consecutively. The other is the Clustered Stacker Crane Problem, in which R is empty and the goal is to find a minimum-weight closed walk that traverses all the arcs in A and services the arcs in A j ( 1 ≤ j ≤ q ) consecutively. For both problems, we propose constant-factor approximation algorithms with ratios 13/6 and 19/6, respectively. [ABSTRACT FROM AUTHOR]