Max-TSP (source code)
= Max-TSP
{c}
= Maximum travelling salesman problem
{synonym}
Find a maximum-weight <Hamiltonian cycle> in a complete weighted <graph> or complete <directed graph>. Nonnegative weights admit a <cycle-cover patching half-approximation for Max-TSP> without a <triangle inequality>. For integer weights, changing $c_{ij}$ to $M-c_{ij}$, with $M\geq\max c_{ij}$, changes an $n$-vertex tour's weight from $C$ to $nM-C$. Consequently the strict-threshold decision version is <NP-complete>: minimum-tour threshold $C\leq L$ becomes maximum-tour threshold $C'>nM-L-1$.
Back to article page
