论文标题
稀疏挖掘中的不对称旅行推销员问题
The Asymmetric Travelling Salesman Problem in Sparse Digraphs
论文作者
论文摘要
不对称的旅行推销员问题（ATSP）及其特殊案例指示的汉密尔顿性是计算机科学中最根本的问题之一。贝尔曼（Bellman），held和karp在60年前开发的动态编程算法$ o^*（2^n）$仍然是这两个问题的最新技术。 在这项工作中，我们专注于稀疏的挖掘图。首先，我们回想起稀疏图中无方向性的汉密尔顿和TSP的已知方法，我们通过适应算法或使用还原来分析它们对定向汉密尔顿和ATSP的后果。通过这种方式，对于几类稀疏的挖掘机，我们获得了许多运行时间上限，包括$ o^*（2^{n/3}）$的digraphs $，具有2个外部和indegree的digraphs，以及$ o^*（3^{n/2}）$，用于digraphs $ for Digraphs for Digraphs for Digraphs for Digraphs contegreie in Degraphs $ bydegbree bunge for-degby byd by 3。 我们的主要结果集中在有限的平均超级$ D $的挖掘上。 ATSP的基线是对周期封面的简单枚举，可以及时完成$ o^*（μ（d）^n）$的函数$μ（d）\ le（\ lceil {d} \ rceil！）还可以观察到，可以在随机时间$ o^*（（（2-2^{ - d}）^n）$和多项式空间中解决定向的汉密尔顿性，通过调整Björklund[Isaac 2018]的最新结果，该结果最初是针对稀疏Biptartite图形中无方向性的。 我们提供了两种针对ATSP的新的确定性算法：第一个在时间$ o（2^{0.441（d-1）n}）$和多项式空间中，第二个在$ o^*（τ（d）^{n/2}）$的运行时间中，第二个在函数$ o^{n/2}）$中的第二个。
Asymmetric Travelling Salesman Problem (ATSP) and its special case Directed Hamiltonicity are among the most fundamental problems in computer science. The dynamic programming algorithm running in time $O^*(2^n)$ developed almost 60 years ago by Bellman, Held and Karp, is still the state of the art for both of these problems. In this work we focus on sparse digraphs. First, we recall known approaches for Undirected Hamiltonicity and TSP in sparse graphs and we analyse their consequences for Directed Hamiltonicity and ATSP in sparse digraphs, either by adapting the algorithm, or by using reductions. In this way, we get a number of running time upper bounds for a few classes of sparse digraphs, including $O^*(2^{n/3})$ for digraphs with both out- and indegree bounded by 2, and $O^*(3^{n/2})$ for digraphs with outdegree bounded by 3. Our main results are focused on digraphs of bounded average outdegree $d$. The baseline for ATSP here is a simple enumeration of cycle covers which can be done in time bounded by $O^*(μ(d)^n)$ for a function $μ(d)\le(\lceil{d}\rceil!)^{1/{\lceil{d}\rceil}}$. One can also observe that Directed Hamiltonicity can be solved in randomized time $O^*((2-2^{-d})^n)$ and polynomial space, by adapting a recent result of Björklund [ISAAC 2018] stated originally for Undirected Hamiltonicity in sparse bipartite graphs. We present two new deterministic algorithms for ATSP: the first running in time $O(2^{0.441(d-1)n})$ and polynomial space, and the second in exponential space with running time of $O^*(τ(d)^{n/2})$ for a function $τ(d)\le d$.
