Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
DOI10.1016/J.EJOR.2003.09.007zbMATH Open1176.90508OpenAlexW1964291347MaRDI QIDQ706963FDOQ706963
Authors: 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
Recommendations
- SOFSEM 2005: Theory and Practice of Computer Science
- On the stability of approximation for Hamiltonian path problems
- Approximation algorithms for multiple terminal, Hamiltonian path problems
- Differential approximation results for the traveling salesman and related problems
- The approximability of the weighted Hamiltonian path completion problem on a tree
Complexity theoryHamiltonian pathsCombinatorial optimizationAnalysis of algorithmsApproximate algorithmsDifferential ratioPerformance ratio
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)
Cites Work
- Printer graphics for clustering
- Title not available (Why is that?)
- Title not available (Why is that?)
- Better approximations for max TSP
- A greedy approximation algorithm for constructing shortest common superstrings
- Title not available (Why is that?)
- Structure preserving reductions among convex optimization problems
- Differential approximation algorithms for some combinatorial optimization problems
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- \(z\)-approximations
- Bounds and Heuristics for Capacitated Routing Problems
- P-Complete Approximation Problems
- The Traveling Salesman Problem with Distances One and Two
- Approximation algorithms for indefinite quadratic programming
- An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit
- Bridging gap between standard and differential polynomial approximation: The case of bin-packing
- Title not available (Why is that?)
- Approximate solution of NP optimization problems
- Completeness in approximation classes
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
- Title not available (Why is that?)
- Non deterministic polynomial optimization problems and their approximations
- Title not available (Why is that?)
- The maximum \(f\)-depth spanning tree problem
- Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
- Heuristic evaluation techniques for bin packing approximation algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation result toward nearest neighbor heuristic
- Differential approximation of NP-hard problems with equal size feasible solutions
Cited In (7)
- The approximability of the weighted Hamiltonian path completion problem on a tree
- Exponential approximation schemata for some network design problems
- On the stability of approximation for Hamiltonian path problems
- SOFSEM 2005: Theory and Practice of Computer Science
- Approximation algorithms for some vehicle routing problems
- Title not available (Why is that?)
- An approximation algorithm for finding long paths in Hamiltonian graphs
This page was built for publication: Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q706963)
