G. [. Alon, M. Gutin, and . Krivelevich, Algorithms with large domination ratio, Journal of Algorithms, vol.50, issue.1, pp.118-131, 2004.
DOI : 10.1016/j.jalgor.2003.09.003

M. G. Ausiello, A. Protasi, G. Marchetti-spaccamela, P. Gambosi, V. Crescenzi et al., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, 1999.
DOI : 10.1007/978-3-642-58412-1

O. [. Bellare, M. Goldreich, and . Sudan, Free bits, PCPs and non-approximability-towards tight results, Proceedings of IEEE 36th Annual Foundations of Computer Science, pp.422-431, 1995.
DOI : 10.1109/SFCS.1995.492573

. D. Bst, S. Berend, Y. Skiena, and . Twitto, Combinatorial dominance guarantees for problems with infeasible solutions. submitted, 2006.

D. Berend, S. Skiena, and Y. Twitto, Dominance certificates for combinatorial optimization problems. submitted, 2006.

G. Gutin, J. Bang-jensen, and A. Yeo, When the greedy algorithm fails, Discrete Optimization, vol.1, issue.2, pp.121-127, 2004.

T. [. Gutin, A. Jensen, and . Yeo, Domination analysis for minimum multiprocessor scheduling, Discrete Applied Mathematics, vol.154, issue.18
DOI : 10.1016/j.dam.2006.02.010

A. [. Glover and . Punnen, The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms, Journal of the Operational Research Society, vol.48, issue.5, pp.502-510, 1997.
DOI : 10.1057/palgrave.jors.2600392

A. [. Gutin, A. Vainshtein, and . Yeo, Domination analysis of combinatorial optimization problems, Discrete Applied Mathematics, vol.129, issue.2-3, 2003.
DOI : 10.1016/S0166-218X(03)00359-7

]. G. Gy01a, A. Gutin, and . Yeo, Polynomial approximation algorithms for the TSP and the QAP with factorial domination number, Discrete Applied Mathematics, 2001.

]. G. Gy01b, A. Gutin, and . Yeo, TSP tour dimination and hamilton cycle decomposition of regular digraphs. Operation Research Letters, 2001.

A. [. Gutin, A. Yeo, and . Zverovich, The Traveling Salesman Problem and its Variations, pp.223-256, 2002.
DOI : 10.1007/b101971

S. [. Hassin, ]. A. Khullerpmk01, F. Punnen, S. Margot, and . Kabadi, z-Approximations, Journal of Algorithms, vol.41, issue.2, pp.429-442, 2001.
DOI : 10.1006/jagm.2001.1187

]. V. Rub73 and . Rublineckii, Estimates of the accuracy of procedures in the traveling salesman problem, Numerical Mathematics and Computer Technology, vol.4, pp.18-23, 1973.

]. V. Sd81a, N. Sarvanov, and . Doroshko, The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of exponential cardinality in quadratic time, Software: Algorithms and Programs (in Russian), pp.8-11, 1981.

]. V. Sd81b, N. Sarvanov, and . Doroshko, The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of factorial cardinality in cubic time, Software: Algorithms and Programs (in Russian), pp.11-13, 1981.

]. E. Zem81 and . Zemel, Measuring the quality of approximate solutions to zero-one programming problems, Mathematics of Operations Research, vol.6, pp.319-332, 1981.