# Lower Bounds on Linear Programming formulations for the Travelling Salesman Problem

**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

**Venue:** Online

**Abstract:**

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

**Dates:**

Wednesday, 13th May 2020 14:30