Seminar talk titled Lower Bounds on Linear Programming formulations for the Travelling Salesman Problem
Title Of the Talk: Lower Bounds on Linear Programming formulations for the Travelling Salesman Problem
Speaker: Dr. Rakesh Venkat, CSE Dept, IITH
Date &Time: Wednesday, 13th May 2020
Linear Programming (LP) based techniques are a central tool in the design of approximation algorithms for NP-Hard problems. The first step in such approaches involves writing a set of linear inequalities (using some variables) to capture (i.e. encode) the solutions to the problem instance within the polytope defined by the feasible region. The ideal goal of such a formulation is to get this polytope to exactly be the convex hull of the encodings of the solutions to the problem.
One might expect, assuming P is not equal to NP, that we can’t achieve this goal using a polynomial-sized LP for NP-hard problems, because optimization over polytopes is possible in time polynomial in the size of the LP.
However, proving such a result is not easy: how does one go about showing that no LP, however cleverly formulated, can do this? Starting with the work of Yannakakis in 1991, this question has seen much progress in recent years, and has revealed connections to a number of other domains including communication complexity, information theory, Fourier analysis and quantum computation along the way.
We will first see a general overview of the results in this area, starting from the basics. I will then present a beautiful (and short) result due to Fiorini et al. that shows that capturing the TSP problem exactly requires exponential-sized LPs.
Main result of the talk is based on the paper: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, by Fiorini, Massar, Pokutta, Tiwary and Wolf (winner of STOC ‘12 Best paper award).
Wednesday, 13th May 2020 14:30