Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)

DOI10.1016/j.ejor.2003.09.007zbMath1176.90508OpenAlexW1964291347MaRDI QIDQ706963

Jérôme Monnot

Publication date: 9 February 2005

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/3743

zbMATH Keywords

Combinatorial optimizationHamiltonian pathsAnalysis of algorithmsComplexity theoryApproximate algorithmsDifferential ratioPerformance ratio

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Exponential approximation schemata for some network design problems ⋮ Approximation algorithms for some vehicle routing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate solution of NP optimization problems
• Approximation algorithms for indefinite quadratic programming
• Completeness in approximation classes
• Heuristic evaluation techniques for bin packing approximation algorithms
• A greedy approximation algorithm for constructing shortest common superstrings
• Structure preserving reductions among convex optimization problems
• Non deterministic polynomial optimization problems and their approximations
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Differential approximation algorithms for some combinatorial optimization problems
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• The maximum \(f\)-depth spanning tree problem
• Better approximations for max TSP
• Bridging gap between standard and differential polynomial approximation: The case of bin-packing
• z-Approximations
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• Bounds and Heuristics for Capacitated Routing Problems
• Printer graphics for clustering
• P-Complete Approximation Problems
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
• Approximation result toward nearest neighbor heuristic
• Differential approximation of NP-hard problems with equal size feasible solutions
• The Traveling Salesman Problem with Distances One and Two

This page was built for publication: Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)