An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit

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

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

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 programming; directed graphs; relaxations; maximum weight Hamiltonian circuit; analysis of approximations; bounds on heuristics; complete, undirected graph with non-negative edge weights; general measure of performance

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C35: Extremal problems in graph theory

65K05: Numerical mathematical programming methods

68R10: Graph theory (including graph drawing) in computer science

05C20: Directed graphs (digraphs), tournaments

05C45: Eulerian and Hamiltonian graphs

Related Items

Differential approximation of NP-hard problems with equal size feasible solutions, Algorithms – ESA 2004, Unnamed Item, An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem, Match twice and stitch: a new TSP tour construction heuristic., Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), Worst-case analysis of two travelling salesman heuristics, Partitioning heuristics for two geometric maximization problems, On the relationship of approximation algorithms for the minimum and the maximum traveling salesman problem, Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem, Maximizing traveling salesman problem for special matrices, An approximation algorithm with performance guarantees for the maximum traveling salesman problem on special matrices, The maximum \(f\)-depth spanning tree problem, Facilities layout generalized model solved by n-boundary shortest path heuristics, Heuristic methods and applications: A categorized survey, Finding maximum square-free 2-matchings in bipartite graphs