*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Ph.D. Thesis Proposal Announcement
Title: LP/SDP Extended formulations: lower bounds and approximation algorithms!
Aurko Roy
Ph.D. Student
Algorithms, Combinatorics, and Optimization
College of Computing
Georgia Institute of Technology
Date: Wednesday, September 14th, 2016
Time: 11 am
Location: ISyE 226A
Committee
----------------
Dr. Sebastian Pokutta (Advisor, School of Industrial & Systems Engineering, Georgia Institute of Technology)
Dr. Dana Randall (School of Computer Science, Georgia Institute of Technology)
Dr. Santanu S. Dey (School of Industrial & Systems Engineering, Georgia Institute of Technology)
Abstract
-----------------------------------------------------------
Linear programs (LPs) and semidefinite programs (SDPs) are the main
components in finding approximately optimal solutions to several
NP-hard optimization problems. A study of the expressive powers of LPs and SDPs is therefore a fundamental endeavor in the field of algorithms and complexity theory.
In the first part, I will present inapproximability results for a variety of (non-CSP) combinatorial optimization problems including Matching, Matching on 3-regular graphs, Sparsest cut (with bounded treewidth on demand graph), Balanced separator and Independent set. (joint with Gabor Braun and Sebastian Pokutta).
In the second part, I will present upper bound results for LPs and SDPs for a few problems. It is well known that several NP-hard problems become easy when the treewidth is bounded. We show analogous results for LPs for problems including Matching, Vertex Cover, Independent set and CSPs (joint with Gabor Braun and Sebastian Pokutta). Additionally, I will present an application of LPs to a problem in machine learning, namely hierarchical clustering. Recently, a cost function was proposed for this problem and it was shown that optimizing over this function recovers the intuitively correct hierarchies in a variety of synthetic examples e.g., planted partitions, cliques, line graphs etc. A top-down algorithm using Sparsest cut as a subroutine was proposed giving an O(log^{3/2}n) approximation (using ARV). I will show how to round an LP relaxation for this problem that gives an approximation factor of O(log n) (joint with Sebastian Pokutta).
