M.Sc Student | Glicksman Hagai |
---|---|

Subject | Approximation Algorithms for the Group Prize Collecting and Location Routing Problems |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Michal Penn |

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.