- On cost matrices with two and three distinct values of Hamiltonian paths and cycles Santosh N. Kabadi (kabadiunb.ca) Abraham P. Punnen (punnenunbsj.ca) Abstract: Polynomially testable characterization of cost matrices associated with a complete digraph on $n$ nodes such that all the Hamiltonian cycles (tours) have the same cost is well known. Tarasov~\cite{TARA81} obtained a characterization of cost matrices where tour costs take two distinct values. We provide a simple alternative characterization of such cost matrices that can be tested in $O(n^2)$ time. We also provide analogous results where tours are replaced by Hamiltonian paths. When the cost matrix is skew-symmetric, we provide polynomially testable characterizations such that the tour costs take three distinct values. Corresponding results for the case of Hamiltonian paths are also given. Using these results, special instances of the asymmetric travelling salesman problem (ATSP) are identified that are solvable in polynomial time and that have improved $\epsilon$-approximation schemes. In particular, we observe that the 3/2 performance guarantee of the Christofides algorithm extends to all metric Hamiltonian symmetric matrices. Further, we identify special classes of ATSP for which polynomial $\epsilon$-approximation algorithms are available for $\epsilon \in \{3/2, 4/3, 4\tau, \frac{3\tau^2}{2}, \frac{4+\delta}{3}\}$ where $\tau > 1/2$ and $\delta \geq 0$ Keywords: Combinatorial optimization, Graphs, traveling salesman problem, approximation algorithms Category 1: Combinatorial Optimization Category 2: Combinatorial Optimization (Approximation Algorithms ) Citation: Technical Report 2004-03, Computational Optimization Laboratory, Department of Mathematical Sciences, University of New Brunswick, Saint John, New Brunswick, Canada Download: [PDF]Entry Submitted: 07/26/2004Entry Accepted: 07/27/2004Entry Last Modified: 07/26/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.