HUJI Combinatorics Seminar 


When: Monday April 26th, 2021, at 10:30AM


Zoom link:

https://huji.zoom.us/j/86972514167?pwd=MDI1U3dTZFFqMnlNcGVrZnR0ZXhKZz09


Speaker:  David Zisselman (HUJI)
Title: TSP approximation on surfaces and manifolds.

Abstract: 

The TSP (travelling salesperson problem) is a well known problem in theoretical CS. Approximation schemes for the Euclidean case are known from the late 90s and in the last decade for the case of a bounded doubling dimension metric as well.

The main drawback of these methods are the lack of flexibility they possess, as, for example, a 4 point metric can be un-embeddable in R^k (for any k) and thus metric spaces that have such a 4 point metric as a subspace can't be solved.

In this talk I'll quickly survey the history and know screams of solutions for TSP and show how our results fit in as a new scream of approximation of TSP.
Later In this talk I'll give a definition of a manifold\surface (which differs from the classical Rimanian geometry definition) and how to approximate TSP on metric spaces induced by such manifolds. 
Finally I'll show embeddings that, together with the approximation scheme, gives a broader family of metric spaces on which TSP could be approximated.