An interior point heuristic for the Hamiltonian cycle problem via Markov decision processes

DOI10.1023/B:JOGO.0000044772.11089.1AzbMATH Open1133.90413OpenAlexW2034738080MaRDI QIDQ1768622FDOQ1768622

Authors: Jacek Gondzio, Vladimir Ejov, Jerzy Filar 

Publication date: 15 March 2005

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/b:jogo.0000044772.11089.1a

Recommendations

• Refined MDP-based branch-and-fix algorithm for the Hamiltonian cycle problem
• Geometric interpretation of Hamiltonian cycles problem via singularly perturbed Markov decision processes
• Hamiltonian cycle problem and Markov chains.
• Finding Hamiltonian cycles using an interior point method
• Markov chains, Hamiltonian cycles and volumes of convex bodies

zbMATH Keywords

interior point methodsnon-convex optimizationHamiltonian cyclesMarkov decision processes

Mathematics Subject Classification ID

Interior-point methods (90C51) Eulerian and Hamiltonian graphs (05C45) Markov and semi-Markov decision processes (90C40) Time-scale analysis and singular perturbations in control/observation systems (93C70)

Cited In (14)

• Refined MDP-based branch-and-fix algorithm for the Hamiltonian cycle problem
• Hamiltonian Cycles and Singularly Perturbed Markov Chains
• Hamiltonian cycle curves in the space of discounted occupational measures
• Feasible Bases for a Polytope Related to the Hamilton Cycle Problem
• Consistent behavior of certain perturbed determinants induced by graphs
• A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem
• Finding Hamiltonian cycles using an interior point method
• A non-standard branch and bound method for the Hamiltonian cycle problem
• Markov chains, Hamiltonian cycles and volumes of convex bodies
• Constrained discounted Markov decision processes and Hamiltonian cycles.
• Proof of the hamiltonicity-trace conjecture for singularly perturbed Markov chains
• A note on using the resistance-distance matrix to solve Hamiltonian cycle problem
• Hamiltonian cycles and subsets of discounted occupational measures
• Geometric interpretation of Hamiltonian cycles problem via singularly perturbed Markov decision processes

This page was built for publication: An interior point heuristic for the Hamiltonian cycle problem via Markov decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1768622)