AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

After a brief introduction to the hyperbolic plane, we turn to studying the traveling salesman problem (TSP). The problem has a PTAS, and we show that a Euclidean algorithm from the early nineties solves it exactly in n^{O(\sqrt{n})} time, which is almost optimal under ETH. We then argue that the interesting instances of TSP in the hyperbolic plane should be sparse enough so that the hyperbolic geometry has an effect. A well-spaced instance is one where the pairwise distance between points is at least some constant. Using a novel separator theorem, we show that hyperbolic TSP on well-spaced point sets can be solved in n^{O(log^2 n)} time, so somewhat surprisingly, the problem may not be NP-hard.

---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Sándor Kisfaludi-Bak

+49 681 9325 0

--email hidden

passcode not visible

logged in users only

Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.