The Symmetric Circulant Traveling Salesman Problem
The Symmetric Circulant Traveling Salesman Problem
复制标题
对称循环旅行商问题
DOI：
10.5772/5581
复制
发表时间：
2008
影响因子：
0.5
通讯作者：
I. Gerace
中科院分区：
文献类型：
--
作者：
F. Greco;I. Gerace
一个n × n的矩阵D = D [i， j]被称为循环矩阵，如果验证(j−i) = k mod n的项D [i， j]对于某些k具有相同的值（关于循环矩阵性质的调查，参见Davis(1979)）。有向图（分别为无向图）是循环的，如果它的邻接矩阵是循环的（分别为对称的和循环的）。同样，如果一个加权图的加权邻接矩阵是循环的，那么它就是循环的。在过去的几年里，人们经常研究当一个图问题被限制在循环图中时是否会变得更容易。例如，如Codenotti等人（1998）所示，当一般实例被强制为循环无向图时，最大团问题和最小图着色问题仍然是NP-hard，并且在常数因子内不可近似。另一方面，Muzychuk（2004）证明了局限于循环无向图的图同构问题在P中，而一般情况下可能更难。有向哈密顿电路问题，限制在循环（有向）图上，是否仍然是np困难的，仍然是一个悬而未决的问题。Garfinkel（1977）、Fan Yang等（1997）和Bogdanowicz（2005）在一些特殊情况下找到了解决方案。相反，哈密顿电路问题允许在循环无向图上使用多项式时间算法，如Burkard和Sandholzer（1991）所示。给出了对称循环矩阵上瓶颈旅行商问题的多项式时间算法。最后，Gilmore等人（1985）证明了最短哈密顿路径问题在循环矩阵上是多项式时间可解的，而一般情况是np困难的。Burkard和Sandholzer（1991）以及Gilmore等人（1985）的积极结果鼓励了对称循环旅行商问题的研究，即限制于对称循环矩阵的和旅行商问题。在本章中，我们处理这样的问题，简称SCTSP。在§1 -§3中引入了这个问题，并且固定了符号。在§4 -§6中概述了过去16年的结果。首先，讨论了一般情况下SCTSP的上界（§4.1）、下界（§4.2）和多项式时间2的近似算法（§4.3）。关于SCTSP的计算复杂度，目前还没有更好的结果。其次，给出了求解SCTSP特殊情况的几个充分定理（§5）。最后，§6专门介绍了最近介绍的SCTSP子案例。§7通过提出尚未解决的问题、评论和未来发展来完成本章。O pe n cc es s D在ab e w w w。我在Lin e. co .网站上
An n × n matrix D = d[i, j] is said to be circulant, if the entries d[i, j] verifying (j − i) = k mod n, for some k, have the same value (for a survey on circulant matrix properties, see Davis (1979)). A directed (respectively, undirected) graph is circulant, if its adjacency matrix is circulant (respectively, symmetric, and circulant). Similarly, a weighted graph is circulant, if its weighted adjacency matrix is circulant. In the last years, it had been often investigated if a graph problem becomes easier when it is restricted to the circulant graphs. For example, the Maximum Clique problem, and the Minimum Graph Coloring problem remain NP-hard, and not approximable within a constant factor, when the general instance is forced to be a circulant undirected graphs, as shown by Codenotti, et al. (1998). On the other hand, Muzychuk (2004) has proved that the Graph Isomorphism problem restricted to circulant undirected graphs is in P, while the general case is, probably, harder. It is still an open question whether the Directed Hamiltonian Circuit problem, restricted to circulant (directed) graphs, remains NP-hard, or not. A solution in some special cases has been found by Garfinkel (1977), Fan Yang, et al. (1997), and Bogdanowicz (2005). The Hamiltonian Circuit problem admits, instead, a polynomial time algorithm on the circulant undirected graphs, as shown by Burkard, and Sandholzer (1991). It leads to a polynomial time algorithm for the Bottleneck Traveling Salesman Problem on the symmetric circulant matrices. Finally, in Gilmore, et al. (1985) it is shown that the Shortest Hamiltonian Path problem is polynomial time solvable on the circulant matrices, while the general case is NP-hard. The positive results contained in Burkard, and Sandholzer (1991), and in Gilmore, et al. (1985) have encouraged the research on the Symmetric Circulant Traveling Salesman problem, that is, the Sum Traveling Salesman Problem restricted to the symmetric, and circulant matrices. In this chapter we deal with such problem, called for short SCTSP. In §1–§3 the problem is introduced, and the notation is fixed. In §4–§6 an overview is given on the last 16 year results. Firstly, an upper bound (§4.1), a lower bound (§4.2), and a polynomial time 2approximation algorithm for the general case of SCTSP (§4.3) are discussed. No better result concerning the computational complexity of SCTSP is known. Secondly, some sufficient theorems solving particular cases of SCTSP are presented (§5). Finally, §6 is devoted to a recently introduced subcase of SCTSP. §7 completes the chapter by presenting open problems, remarks, and future developments. O pe n A cc es s D at ab as e w w w .ite ch on lin e. co m