由按列单降矩阵给出的瓶颈TSP的一个迭代算法

摘要

本文给出了一个求解由按列单降矩阵(Matrices graded up its columns)给出的瓶颈旅行商问题(Bottleneck TSP)的迭代算法,证明了算法是可实现的且只需要多项式界的迭代时间。算法揭示了这类问题的一个极好性质,即任意2—邻域内的最优解必为同题的全局最优解。