An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit

Abstract

We give bounds on heuristics and relaxations for the problem of determining a maximum weight hamiltonian circuit in a complete, undirected graph with non-negative edge weights. Three well-known heuristics are shown to produce a tour whose weight is at least half of the weight of an optimal tour. Another heuristic, based on perfect two-matchings, is shown to produce a tour whose weight is at least two-thirds of the weight of an optimal tour. Assignment and perfect two-matching relaxations are shown to produce upper bounds that are, respectively, at most 2 and 3/2 times the optimal value. By defining a more general measure of performance, we extend the results to arbitrary edge weights and minimization problems. We also present analogous results for directed graphs.