KAM-DIMATA Series 2004-657 and ITI Series 2004-180. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

0106814 - MU-W 20040021 RIV CZ eng V - Research Report
Blaser, M. - Manthey, B. - Sgall, Jiří
KAM-DIMATA Series 2004-657 and ITI Series 2004-180. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality.
[Zlepšený aproximační algoritmus pro asymetrický problém obchodního cestujícího.]
Praha: Charles University, 2004. 11 s.
R&D Projects: GA AV ČR IAA1019401; GA MŠMT LN00A056
Institutional research plan: CEZ:AV0Z1019905
Keywords : combinatorial algorithms * graph theory
Subject RIV: BA - General Mathematics

We consider the asymmetric traveling salesperson problem with /gamma-parameterized triangle inequality Chandran and Ram recently gave the first constant factor approximation algorithm with polynomial running time for this problem. We devise an approximation algorithm, which is better than the one of Chandran and Ram for /gamma in [0.5437,1).

Článek navrhuje zlepšený aproximační algoritmus pro asymetrický problém obchodního cestujícího.
Permanent Link: http://hdl.handle.net/11104/0013988