An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
DOI10.1287/OPRE.27.4.799zbMATH Open0412.90070OpenAlexW2172285784MaRDI QIDQ4199854FDOQ4199854
Authors: Marshall L. Fisher, G. L. Nemhauser, Laurence A. Wolsey 
Publication date: 1979
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.27.4.799
directed graphsrelaxationsnetwork programmingmaximum weight Hamiltonian circuitanalysis of approximationsbounds on heuristicscomplete, undirected graph with non-negative edge weightsgeneral measure of performance
Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)
Cited In (26)
- Facilities layout generalized model solved by n-boundary shortest path heuristics
- Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
- On the maximum TSP with \(\gamma\)-parameterized triangle inequality
- Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
- Algorithms – ESA 2004
- Differential approximation results for the traveling salesman and related problems
- Match twice and stitch: a new TSP tour construction heuristic.
- On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem
- An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices
- An approximation algorithm for maximum packing of 3-edge paths
- Algorithms as Mechanisms: The Price of Anarchy of Relax and Round
- Heuristic methods and applications: A categorized survey
- An approximation algorithm for the maximum traveling salesman problem
- An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem
- Title not available (Why is that?)
- Maximizing traveling salesman problem for special matrices
- Finding maximum square-free 2-matchings in bipartite graphs
- The maximum \(f\)-depth spanning tree problem
- Polyhedron of triangle-free simple 2-matchings in subcubic graphs
- Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem
- Worst-case analysis of two travelling salesman heuristics
- Partitioning heuristics for two geometric maximization problems
- Finding triangle-free 2-factors in general graphs
- Differential approximation of NP-hard problems with equal size feasible solutions
- An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem
- Informative path planning as a maximum traveling salesman problem with submodular rewards
This page was built for publication: An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4199854)
