Název: KAM-DIMATA Series 2004-657 and ITI Series 2004-180. An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
Překlad názvu: Zlepšený aproximační algoritmus pro asymetrický problém obchodního cestujícího
Autoři: Blaser, M. ; Manthey, B. ; Sgall, Jiří
Typ dokumentu: Výzkumné zprávy
Rok: 2004
Jazyk: eng
Abstrakt: [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.
Klíčová slova: combinatorial algorithms; graph theory
Číslo projektu: CEZ:AV0Z1019905 (CEP), IAA1019401 (CEP), LN00A056 (CEP)
Poskytovatel projektu: GA AV ČR, GA MŠk

Instituce: Matematický ústav AV ČR (web)
Informace o dostupnosti dokumentu: Dokument je dostupný v příslušném ústavu Akademie věd ČR.
Původní záznam: http://hdl.handle.net/11104/0013988

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-20177


Záznam je zařazen do těchto sbírek:
Věda a výzkum > AV ČR > Matematický ústav
Zprávy > Výzkumné zprávy