Bilkent University
Department of Computer Engineering
S E M I N A R
New Tools and Algorithms for Graph Partitioning Problems
Dr. Ali Kemal Sinop
Simons Institute
Clustering and graph partitioning are two tasks commonly arising in many areas, including machine learning, data mining, computer vision, web search and scientific computing. Being NP-hard in general, these problems received much attention from an approximation point of view: Can we always find a solution whose cost is close to the optimum (approximability)? At what point does even the approximation problem become NP-hard (hardness of approximation)?
In the first part of my talk, I will present an approximation algorithm for many combinatorial optimization problems based on rounding fractional solutions obtained from certain hierarchies of Semi-definite Programming relaxations. Prior to our work, no positive result for such hierarchies were known. I will show a surprising connection between the analysis of our rounding algorithm with the problem of column based matrix reconstruction, for which I will describe an optimal algorithm.
In the last part of my talk, I will discuss a new algorithm for spectral k-clustering problem. Prior to our work, all known algorithms and heuristics suffered from two major drawbacks: 1) The quality of solution deteriorated quickly as k increased (approximation guarantee of Ω(k OPT)). 2) Only large clusters were guaranteed to be found. We give the first algorithm whose quality is independent of both the number of clusters as well as the cluster sizes with an approximation factor of O(√OPT ) .
Bio: Dr. Ali Kemal Sinop is currently a research fellow at the Simons Institute for Theory of Computing, UC Berkeley. Prior to Berkeley, he spent a year as a member of the School of Mathematics at the Institute for Advanced Study. Before that he was a post-doctoral research scientist at the Center for Computational Intractability, Princeton University. He received his PhD in computer science from the Computer Science Department of Carnegie Mellon University in 2012 under the supervision of Prof. Venkatesan Guruswami. Before his PhD, he worked at Siemens Corporate Research from 2005 to 2007. His research interests are in the area of theoretical computer science, particularly approximation algorithms, hardness of approximation; and spectral graph theory.
DATE: 04 June, 2015, Thursday @ 13:40
PLACE: EA-409