论文标题
图中TSP实例的平均解决方案
The average solution of a TSP instance in a graph
论文作者
论文摘要
我们将图$ g $的平均$ k $ -tsp距离$μ__{tsp，k} $定义为最短步行访问$ k $ vertices的平均长度，即具有$ k $均匀随机随机选择的随机TSP实例的预期解决方案。我们证明了与平均$ k $ steiner距离的关系，并表征了发生平等的情况。给定图的顺序，我们还为$μ_{tsp，k}（g）$提供了尖锐的界限。
We define the average $k$-TSP distance $μ_{tsp,k}$ of a graph $G$ as the average length of a shortest walk visiting $k$ vertices, i.e. the expected length of the solution for a random TSP instance with $k$ uniformly random chosen vertices. We prove relations with the average $k$-Steiner distance and characterize the cases where equality occurs. We also give sharp bounds for $μ_{tsp,k}(G)$ given the order of the graph.
