Abstract | ||
---|---|---|
Abstract 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. |
Year | DOI | Venue |
---|---|---|
2001 | 10.1016/S1571-0653(04)00220-3 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
bipartite TSP | Discrete mathematics,Approximation algorithm,Combinatorics,Bipartite graph,Travelling salesman problem,Euclidean geometry,Unit square,Mathematics,Frieze | Journal |
Volume | ISSN | Citations |
7 | 1571-0653 | 1 |
PageRank | References | Authors |
0.38 | 3 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andreas Baltz | 1 | 30 | 6.68 |
Tomasz Schoen | 2 | 36 | 12.04 |
Anand Srivastav | 3 | 248 | 36.81 |