Hi, my name is Omer Wasim and am glad to meet you via my project webpage. My interests broadly lie in theoretical computer science and more specifically in the design and analysis of algorithms. My supervisor for this project is Dr Hubert Chan. The second examiner for this project is Dr H.F. Ting.
You can find the detailed project plan here.
Cut-based graph theoretic problems encompass some of the most seminal problems in theoretical computer science, having wide ranging applications within and beyond computing. The standard graph partitioning seeks to partition a graph G = (V,E) into k pieces where k<=n=|V| while fulfilling a balance condition on the size of each piece. The goal is to minimize the edges that cross from one piece to another. Unfortunately, this problem and many of its variants are NP-complete. The set of closely related problems includes finding a balanced cut, maximum-cut and sparsest cut in a weighted undirected graph1. In this thesis, we study various NP-hard graph partitioning problems. The overarching goals of this thesis are: 1) to survey several breakthrough techniques in convex and continuous optimization (such as linear programming, semidefinite programming and eigenvalue optimization) that have been successfully applied to get provably good solutions for fundamental problems in combinatorial optimization and theoretical computer science and 2) to provide empirical evidence of the quality of approximation ratios obtained by employing such techniques to solve the maximum cut and sparsest cut problems in real world problem instances.
The final report for this project can be downloaded here. Your comments are very much welcome as are any pointers to errors and/or omissions.
Slides of the final presentation can be download here.
If you have any questions and/or feedback, please do not hesitate to get in touch at omerwa90@connect.hku.hk.