Create accountLogin

Recent searches

No recent searches

Search options

Only available when logged in.
mathstodon.xyz is one of the many independent Mastodon servers you can use to participate in the fediverse.
A Mastodon instance for maths people. We have LaTeX rendering in the web interface!

Administered by:

Server stats:

2.8K
active users

mathstodon.xyz: AboutStatusProfiles directoryPrivacy policy

Mastodon: AboutGet the appKeyboard shortcutsView source codev4.3.7

Public
0xDE

A quasi-polynomial algorithm for well-spaced hyperbolic TSP: arxiv.org/abs/2002.05414

This new preprint by Sándor Kisfaludi-Bak (accepted to SoCG) just came out and caught my attention. TSP is NP-hard for Euclidean points or close-together hyperbolic points. This paper shows that it's much easier when the points are widely spaced in the hyperbolic plane. The idea is to separate the input by a short line segment that the solution crosses few times and apply dynamic programming.

arxiv.orgA quasi-polynomial algorithm for well-spaced hyperbolic TSPWe study the traveling salesman problem in the hyperbolic plane of Gaussian curvature $-1$. Let $α$ denote the minimum distance between any two input points. Using a new separator theorem and a new rerouting argument, we give an $n^{O(\log^2 n)\max(1,1/α)}$ algorithm for Hyperbolic TSP. This is quasi-polynomial time if $α$ is at least some absolute constant, and it grows to $n^{O(\sqrt{n})}$ as $α$ decreases to $\log^2 n/\sqrt{n}$. (For even smaller values of $α$, we can use a planarity-based algorithm of Hwang et al. (1993), which gives a running time of $n^{O(\sqrt{n})}$.)
Public
Refurio Anachro

This is the second time I read about a problem becoming easier in hyperbolic space. I forgot the other one, I'll have to hunt for it! I can see what's happening with TSP here - there must be more problems like this! Thanks for inspiring!

@11011110

0xDE

@RefurioAnachro The other one that comes to mind for me is greedy embedding (en.wikipedia.org/wiki/Greedy_e) where every graph has one in the hyperbolic plane but not even a six-leaf star has one in the Euclidean plane.

en.wikipedia.orgGreedy embedding - Wikipedia
Feb 15, 2020, 05:47 PM·Public·Web
0boosts·2favorites
Public
Refurio Anachro

Thanks, @11011110, that wasn't it, so there should be yet another one :) I'll make sure to tag you when I my collection grows.

SearchLive feeds
About