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

DOI10.1023/B:JOGO.0000044772.11089.1AMaRDI QIDQ1768622zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(14)

• Geometric interpretation of Hamiltonian cycles problem via singularly perturbed Markov decision processes
• 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

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)