search query: @indexterm Travelling salesman problem / total: 62
reference: 1 / 62
« previous | next »
| Author: | Monnot, J. Paschos, C.Th. Toulouse, S. |
| Title: | Differential approximation results for the traveling salesman problem with distances 1 and 2 |
| Journal: | European Journal of Operational Research
2003 : MAR 16, VOL. 145:3, p. 557-568 |
| Index terms: | Algorithms Optimization Travelling salesman problem |
| Language: | eng |
| Abstract: | The authors prove that both minimum and maximum traveling salesman problems on complete graphs with edge-distances 1 and 2 (denoted by min_TSP12 and max_TSP12, respectively) are approximable within 3/4. Based upon this result, they improve the standard-approximation ratio known for maximum traveling salesman with distances 1 and 2 from 3/4 to 7/8. |
« previous | next »
SCIMA