An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit

DOI10.1287/OPRE.27.4.799MaRDI QIDQ4199854zbMATHOpenAlexFDO

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

zbMATH Keywords

directed graphsrelaxationsnetwork programmingmaximum weight Hamiltonian circuitanalysis of approximationsbounds on heuristicscomplete, undirected graph with non-negative edge weightsgeneral measure of performance

Mathematics Subject Classification ID

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
• Differential approximation of NP-hard problems with equal size feasible solutions
• On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem
• Algorithms – ESA 2004
• An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem
• Finding maximum square-free 2-matchings in bipartite graphs
• The maximum \(f\)-depth spanning tree problem
• An approximation algorithm for maximum packing of 3-edge paths
• Differential approximation results for the traveling salesman and related problems
• Worst-case analysis of two travelling salesman heuristics
• On the maximum TSP with \(\gamma\)-parameterized triangle inequality
• An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• Informative path planning as a maximum traveling salesman problem with submodular rewards
• Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
• An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem
• Finding triangle-free 2-factors in general graphs
• Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
• Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem
• Match twice and stitch: a new TSP tour construction heuristic.
• Algorithms as mechanisms: the price of anarchy of relax and round
• Partitioning heuristics for two geometric maximization problems
• scientific article; zbMATH DE number 2230217 (Why is no real title available?)
• An approximation algorithm for the maximum traveling salesman problem
• Heuristic methods and applications: A categorized survey
• Maximizing traveling salesman problem for special matrices

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)