Pobabilistic Analysis of Bipartite Traveling Salesman Problems (Extended Abstract)

详细信息    查看全文

• 作者：Andreas Baltz ; Tomasz Schoen ; An ; Srivastav
• 关键词：bipartite TSP
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2001
• 出版时间：April 2001
• 年：2001
• 卷：7
• 期：Complete
• 页码：42-45
• 全文大小：324 K

文摘

We consider two kinds of random settings of the bipartite TSP. For the asymmetric TSP we generalize a result of Frieze, Karp, and Reed concerning the relationship between the TSP and its assignment relaxation. Turning to the Euclidean bipartite TSP in the unit square we give an approximation algorithm for finding a short tour efficiently in parallel.