טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGlicksman Hagai
SubjectApproximation Algorithms for the Group Prize Collecting
and Location Routing Problems
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Michal Penn


Abstract

In this work we develop approximation algorithms for generalizations of the following three known combinatorial optimization problems, the Prize-Collecting Steiner Tree, the Prize-Collecting Travelling Salesman Problem and a Location Routing problem.


Given G=(V,E) and a length function on its edges, in the grouped versions of the above mentioned problems we assume that V is partitioned into k+1 groups, {V0, V1, … Vk},  with a penalty function on the groups.

In the Group Prize-Collecting Steiner Tree problem the aim is to find S, a collection of groups of V and a tree spanning the rest of the groups not in S, so as to minimize  the sum of the costs of the edges in the tree and the costs of the groups in S. 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.


The three algorithms follow the same general scheme  where at the irst stage a selected set of representatives is chosen by solving an appropriate LP relaxation of a given problem and then, relative to this set, the required network is constructed using Goemans and Williamson's primal-dual approximation algorithm for the PCST problem.
The three approximation factors achieved are identical and equal (2 -1/(n-1))I, where I is the cardinality of
the largest group.