An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit

M. L. Fisher, G. L. Nemhauser and L. A. Wolsey
Additional contact information
M. L. Fisher: University of Pennsylvania, Philadelphia, Pennsylvania
G. L. Nemhauser: Cornell University, Ithaca, New York
L. A. Wolsey: University of Louvain, Louvain-La-Neuve, Belgium

Operations Research, 1979, vol. 27, issue 4, 799-809

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.

Date: 1979
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.27.4.799 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:27:y:1979:i:4:p:799-809

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().