= Cycle-cover patching half-approximation for Max-TSP
{title2=$\operatorname{ALG}\geq\tfrac12\operatorname{OPT}$}
Solve the maximum-weight <assignment problem> forbidding fixed points, obtaining a <cycle cover of a directed graph> whose weight bounds every <Hamiltonian cycle> above. Remove a lightest <edge> from each <graph cycle>. Each <graph cycle> has at least two <edges>, so at least half its nonnegative weight survives. Connect the resulting disjoint <graph paths> cyclically; completeness supplies the connectors and their nonnegative weights cannot reduce the retained sum. The <Hungarian algorithm> and linear-time patching give a <polynomial time> <approximation algorithm>. Negative weights invalidate a universal multiplicative half guarantee: when every weight is $-1$, every tour has weight $-n<(-n)/2$.
Back to article page
