Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 1998 Copyright 1998 University of Bonn, Department of Computer Science, Abt. V
8945

On Approximation Hardness of Dense TSP and other Path Problems
W. Fernandez de la Vega, Marek Karpinski
[Download PostScript] [Download PDF]

TSP(1,2) is the problem of finding a tour with minimum length in a complete weighted graph where each edge has length 1 or 2. Let $d_o$ satisfy $0

Last Change: 11/05/14 at 10:12:45
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V