Leírás
Abstract: The metric traveling salesman problem has received a lot of attention in the past couple of years, and we will discuss some of the recent results. These efforts are towards the improvement of the 3/2 approximation guarantee of the well-known Christofides algorithm. In 2018, Haddadan, Newman, and Ravi proved that in a 3-edge-connected 3-regular graph there is a convex combination of tour vectors so that every edge has a value at most 18/19. This implies a 27/19-approximation for TSP, in the case when the all-2/3 vector happens to be an optimum solution of the subtour elimination LP. In 2019, Karlin, Klein, and Oveis Gharan proved that in a 4-regular 4-edge-connected graph there is a convex combination of tour vectors so that every edge has a value at most 0.749965. This implies a 1.49993-approximation for TSP, in the case when the optimum solution of the subtour elimination LP happens to be half-integral. In 2020, by generalizing their methods, Karlin, Klein, and Oveis Gharan claim that for metric TSP there is a 1.5-10^{-36} approximation, thus becoming the first one to improve on Christofides' bound. Both of these papers build upon the machinery of choosing a spanning tree from a maximum entropy distribution, devised by Oveis Gharan, Saberi, and Singh.
After the talk, there will be a short virtual meeting with free discussion on any topic.
Please contact Tamás Király (tkiraly[at]cs.elte.hu) for Zoom access if you are not on the mailing list.