Date: Wednesday 17:30-18:30, February 27th

Improved inapproximability for TSP: the role of bounded occurrence CSPs
Michail Lampis (KTH Royal Institute of Technology)

The Traveling Salesman problem is one of the most famous problems in
combinatorial optimization and its approximability is a huge open
problem.  Though there have been recent breakthroughs on the
algorithmic side, until recently the best inapproximability constant
was only 220/219, due to Papadimitriou and Vempala.  In this talk we
will sketch a much simpler reduction which achieves a slightly better
inapproximability bound.  The main ingredient is inapproximable
constraint satisfaction problems where each variable only appears a
bounded number of times.  We will discuss the role of expanders and
amplifier graphs in the inapproximability of such problems and outline
a simple (but hard to analyze) idea which allows us to obtain better
expander graphs using the probabilistic method, improving on a 25-year
old result by Bollobas.  Finally, we will discuss whether it is
realistic to hope that further work in this direction might eventually
lead to a strong inapproximability result for TSP (spoiler: probably
not!).

問合せ先：河村（A01）