Original title: KAM-DIMATA Series 2004-657 and ITI Series 2004-180. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
Translated title: Zlepšený aproximační algoritmus pro asymetrický problém obchodního cestujícího
Authors: Blaser, M. ; Manthey, B. ; Sgall, Jiří
Document type: Research reports
Year: 2004
Language: eng
Abstract: [eng] [cze]
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.
Keywords: combinatorial algorithms; graph theory
Project no.: CEZ:AV0Z1019905 (CEP), IAA1019401 (CEP), LN00A056 (CEP)
Funding provider: GA AV ČR, GA MŠk

Institution: Institute of Mathematics AS ČR (web)
Document availability information: Fulltext is available at the institute of the Academy of Sciences.
Original record: http://hdl.handle.net/11104/0013988

Permalink: http://www.nusl.cz/ntk/nusl-20177


The record appears in these collections:
Research > Institutes ASCR > Institute of Mathematics
Reports > Research reports