Approximation algorithms for group prize-collecting and location-routing problems

In this paper we develop approximation algorithms for generalizations of the following three known combinatorial optimization problems, the Prize-Collecting Steiner Tree problem, the Prize-Collecting Travelling Salesman Problem and a Location-Routing problem.Given a graph G=(V,E)G=(V,E) on nn vertices and a length function on its edges, in the grouped versions of the above mentioned problems we assume that VV is partitioned into k+1k+1 groups, {V0,V1,…,Vk}{V0,V1,…,Vk}, with a penalty function on the groups. In the Group Prize-Collecting Steiner Tree problem the aim is to find SS, a collection of groups of VV and a tree spanning the rest of the groups not in SS, so as to minimize the sum of the costs of the edges in the tree and the costs of the groups in SS. The Group Prize-Collecting Travelling Salesman Problem, is defined analogously. In the Group Location-Routing problem the customer vertices are partitioned into groups and one has to select simultaneously a subset of depots to be opened and a collection of tours that covers the customer groups. The goal is to minimize the costs of the tours plus the fixed costs of the opened depots. We give a (2−1n−1)I-approximation algorithm for each of the three problems, where II is the cardinality of the largest group.