An analysis of approximations for finding a maximum weight Hamiltonian circuit
(1979) Operations research — Vol. 27, p. 799-809 (1979)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 320.89 KB
Details
- Authors
- 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.
- Affiliations
Citations
Fisher, M. L., Nemhauser, G. L., & Wolsey, L. (1979). An analysis of approximations for finding a maximum weight Hamiltonian circuit. Operations research, 27, 799-809. https://hdl.handle.net/2078.5/35919 (Original work published 1979)