haku: @indexterm ALGORITHMS / yhteensä: 403
viite: 24 / 403
| Tekijä: | Monnot, J. Paschos, C.Th. Toulouse, S. |
| Otsikko: | Differential approximation results for the traveling salesman problem with distances 1 and 2 |
| Lehti: | European Journal of Operational Research
2003 : MAR 16, VOL. 145:3, p. 557-568 |
| Asiasana: | Algorithms Optimization Travelling salesman problem |
| Kieli: | eng |
| Tiivistelmä: | 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. |
SCIMA