  


On cost matrices with two and three distinct values of Hamiltonian paths and cycles
Santosh N. Kabadi (kabadiunb.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 skewsymmetric, 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 200403, Computational Optimization Laboratory, Department of Mathematical Sciences, University of New Brunswick, Saint John, New Brunswick, Canada Download: [PDF] Entry Submitted: 07/26/2004 Modify/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  