An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit

DOI10.1287/opre.27.4.799zbMath0412.90070OpenAlexW2172285784MaRDI QIDQ4199854

Laurence A. Wolsey, Marshall L. Fisher, Nemhauser, George I.

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

network programmingdirected graphsrelaxationsmaximum weight Hamiltonian circuitanalysis of approximationsbounds on heuristicscomplete, undirected graph with non-negative edge weightsgeneral measure of performance

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items

On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem, An approximation algorithm for maximum packing of 3-edge paths, Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems, An approximation algorithm for the maximum traveling salesman problem, Differential approximation results for the traveling salesman and related problems, Maximizing traveling salesman problem for special matrices, Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem, An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem, Polyhedron of triangle-free simple 2-matchings in subcubic graphs, On the maximum TSP with \(\gamma\)-parameterized triangle inequality, Match twice and stitch: a new TSP tour construction heuristic., Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), Finding maximum square-free 2-matchings in bipartite graphs, An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem, Algorithms – ESA 2004, Differential approximation of NP-hard problems with equal size feasible solutions, Facilities layout generalized model solved by n-boundary shortest path heuristics, Heuristic methods and applications: A categorized survey, Unnamed Item, Algorithms as Mechanisms: The Price of Anarchy of Relax and Round, Worst-case analysis of two travelling salesman heuristics, Partitioning heuristics for two geometric maximization problems, Informative path planning as a maximum traveling salesman problem with submodular rewards, An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices, The maximum \(f\)-depth spanning tree problem