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 - Výzkumná zpráva
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.
Grant CEP: GA AV ČR IAA1019401; GA MŠMT LN00A056
Výzkumný záměr: CEZ:AV0Z1019905
Klíčová slova: combinatorial algorithms * graph theory
Kód oboru RIV: BA - Obecná matematika

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.
Trvalý link: http://hdl.handle.net/11104/0013988