Wenceslas Fernandez de la Vega, Marek Karpinski

TSP(1,2), the Traveling Salesman Problem with distances 1 and 2, is

the problem of finding a tour of minimum length in a complete

weighted graph where each edge has length 1 or 2. Let $d_o$ satisfy

$0<d_o<1/2$. We show that TSP(1,2) has no PTAS on the set ...
more >>>

Tomas Feder, Rajeev Motwani

We show how to find in Hamiltonian graphs a cycle of length

$n^{\Omega(1/\log\log n)}$. This is a consequence of a more general

result in which we show that if $G$ has maximum degree $d$ and has a

cycle with $k$ vertices (or a 3-cyclable minor $H$ with $k$ vertices),

then ...
more >>>