The probabilistic relationship between the assignment and asymmetric traveling salesman problems. (Q2768360)

Relations between assignment (AP) and asymmetric traveling salesman problems (ATSP) are investigated. If the cost matrix of the two problems are random numbers, lower and upper bounds for the objective functions values and for the maximum cost edges used in an optimal solution are known from the literature. These bounds are improved. As in previous papers the proofs of these bounds is obtained by analyzing an \(O(n^3)\) heuristic which patches an optimal AP solution into a ``good'' ATSP solution. Moreover, it is shown that a random instance of the ATSP can be solved exactly in \(e^{\widetilde O(\sqrt n)}\), where the \(\widetilde O\) denotation indicates that logarithmic factors are ignored.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].