טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentYuval Michael
SubjectGraph Clustering to Minimize the Sum of Radii with Fixed
Costs
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Levin Asaf
Full Thesis textFull thesis text - English Version


Abstract

We study the problem of clustering vertices of a graph with a distance function on its edges, so as to minimize the sum of clusters' radii and fixed establishment costs. This problem is NP-hard and therefore many approximation algorithms have been designed. Charikar and Panigrahy introduced a primal dual algorithm which achieves an approximation factor of 3, the current best factor.

We present a heuristic algorithm based on the linear programming formulation of the problem. We present also a heuristic algorithm based on a local search approach, which starts with an initial feasible solution of clusters, and at each step the solution can be modified by adding, deleting or replacing one existing cluster. We prove that the approximation ratios of the two heuristics are not bounded.

Next, we study a new variant of the problem, where vertices are required to be covered by at least two clusters. We design a polynomial time (exact) algorithm based on a dynamic programming approach, for special types of graphs. These types of graphs are paths, trees and bounded tree width graphs. The time complexity of the algorithms deteriorates as we move from paths to trees and bounded tree width graphs. At last, we present an interesting property of a centroid in a shortest path tree of a graph. Namely, we show that for each connected, undirected graph with non-negative weight of the vertices, there exists a vertex u with a shortest path tree Tu from u, where u is the centroid of Tu.