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

Result code in IS VaVaI

RIV/67985840:_____/04:00106814 - isvavai.cz

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

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

Original language description

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).

Czech name

Zlepšený aproximační algoritmus pro asymetrický problém obchodního cestujícího

Czech description

Článek navrhuje zlepšený aproximační algoritmus pro asymetrický problém obchodního cestujícího.

Type

V_x - Unclassified - Research report containing classified information

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2004

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Number of pages

11

Place of publication

Praha

Publisher/client name

Neuveden

Version

—