|Ph.D Student||Schwartz Roy|
|Subject||Labelings and Partitions of Graphs|
|Department||Department of Computer Science||Supervisor||Professor Joseph Naor|
|Full Thesis text|
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.