PhD Proposal by Aurko Roy

Event Details
  • Date/Time:
    • Wednesday September 14, 2016 - Thursday September 15, 2016
      11:00 am - 12:59 pm
  • Location: ISyE 226A
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: LP/SDP Extended formulations: lower bounds and approximation algorithms!

Full Summary: No summary paragraph submitted.

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

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)


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). 


Additional Information

In Campus Calendar

Graduate Studies

Invited Audience
Phd proposal
  • Created By: Tatianna Richardson
  • Workflow Status: Draft
  • Created On: Sep 1, 2016 - 9:40am
  • Last Updated: Oct 7, 2016 - 10:19pm