Loading...
Please wait, while we are loading the content...
Similar Documents
Worst case performance of approximation algorithm for asymmetric tsp (2003).
| Content Provider | CiteSeerX |
|---|---|
| Author | Palbom, Anna |
| Abstract | In 1982 Frieze, Galbiati and Maffioli [3] invented their famous algorithm for approximating the TSP tour in an asymmetric graph. They show that the algorithm approximates the TSP tour within a factor of log n. We construct a family of graphs for which the algorithm (with some implementation details specified by us) gives an approximation in Ω(log n). This shows that the analysis by Frieze et al. is tight up to a constant factor and can hopefully give deeper understanding of the problem. 1 |
| File Format | |
| Publisher Date | 2003-01-01 |
| Access Restriction | Open |
| Subject Keyword | Asymmetric Tsp Implementation Detail Asymmetric Graph Famous Algorithm Approximation Algorithm Constant Factor Worst Case Performance Tsp Tour |
| Content Type | Text |
