Ph.D Thesis

Ph.D StudentSchwartz Roy
SubjectLabelings and Partitions of Graphs
DepartmentDepartment of Computer Science
Supervisor PROF. Joseph Naor
Full Thesis textFull thesis text - English Version


Graph partitioning and labeling problems are perhaps one of the most well studied type of combinatorial optimization problems. Such problems are motivated by a wide range of applications, including: sparse linear system solving in scientific computing, circuit testing and simulation in VLSI design, resource allocation in parallel computing, data mining and clustering, social network analysis, pattern recognition in computer vision and network design. Specifically, balanced graph partitioning problems are used as a basic subroutine in the design of other algorithms and in many divide-and-conquer heuristics. The current techniques used to tackle these problems exhibit a deep and rich connection with other disciplines such as geometry, probability, functional analysis and complexity theory. In this thesis we consider several balanced graph partitioning and labeling problems for which we present improved approximation algorithms.