Optimization Online


On cost matrices with two and three distinct values of Hamiltonian paths and cycles

Santosh N. Kabadi (kabadi***at***unb.ca)
Abraham P. Punnen (punnen***at***unbsj.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/2004
Entry Accepted: 07/27/2004
Entry Last Modified: 07/26/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society