Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number (Q1602705): Difference between revisions

Using derandomization, the authors present the Greedy-Expectation Algorithm (GEA), a general polynomial approximation algorithm for combinatorial problems. For the TSP with \(n\) vertices it leads to an approximation algorithm with domination number at least \((n-2)!\), that is, there are at least \((n-2)!\) tours not better than the one generated by GEA. They mention that, in particular, this disproves a conjecture of \textit{F. Glover} and \textit{A. P. Punnen} [J. Oper. Res. Soc. 48, 502-510 (1997; Zbl 0882.90124)]. For the quadratic assignment problem (QAP) the GEA leads again to a polynomial approximation algorithm with domination number at least \((n-2)!\) provided that the number \(n\) of vertices is a prime power. For QAP they show that for all \(\beta>1\) and every sufficiently large \(n\) the domination number is at least \(n!/\beta^n\).