Thumbnail

A Note on Using T-joins to Approximate Solutions for min Graphic k-Path TSP

Kheffache, Rezika; Giannakos, Aristotelis (2012-12), A Note on Using T-joins to Approximate Solutions for min Graphic k-Path TSP. https://basepub.dauphine.fr/handle/123456789/12147

View/Open
Type
Document de travail / Working paper
Date
2012-12
Publisher
Université Paris-Dauphine
Series title
Cahiers du Lamsade
Series number
329
Published in
Paris
Pages
11
Metadata
Show full item record
Author(s)
Kheffache, Rezika
Université Mouloud Mammeri [Tizi Ouzou] [UMMTO]
Giannakos, Aristotelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We consider a generalized Path Traveling Salesman Problem where the distances are defined by a 2-edge-connected graph metric and a constant number of salesmen have to cover all the destinations by traveling along paths of minimum total length. We show that for this problem there is a polynomial algorithm with asymptotic approximation ratio of 3/2.
Subjects / Keywords
Algorithme et structure de données; Complexité; Recherche opérationnelle