Combinatorial dominance guarantees for problems with infeasible solutions

ABSTRACT

The design and analysis of approximation algorithms for NP-hard problems is perhaps the most active research area in the theory of combinatorial algorithms. In this article, we study the notion of a combinatorial dominance guarantee as a way for assessing the performance of a given approximation algorithm. An f(n) dominance bound is a guarantee that the heuristic always returns a solution not worse than at least f(n) solutions. We give tight analysis of many heuristics, and establish novel and interesting dominance guarantees even for certain inapproximable problems and heuristic search algorithms. For example, we show that the maximal matching heuristic of VERTEX COVER offers a combinatorial dominance guarantee of 2ⁿ − (1.839 + o(1))ⁿ. We also give inapproximability results for most of the problems we discuss.

REFERENCES

• 1: Noga Alon , Gregory Gutin , Michael Krivelevich, Algorithms with large domination ratio, Journal of Algorithms, v.50 n.1, p.118-131, January 2004 [doi>10.1016/j.jalgor.2003.09.003]
• 2: Egon Balas , Neil Simonetti, Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study, INFORMS Journal on Computing, v.13 n.1, p.56-75, December 2000 [doi>10.1287/ijoc.13.1.56.9748]
• 3: M. Bellare , O. Goldreich , M. Sudan, Free bits, PCPs and non-approximability-towards tight results, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.422, October 23-25, 1995
• 4: Berend, D., Skiena, S., and Twitto, Y. 2006. Dominance certificates for combinatorial optimization problems. submitted.
• 5: Deineko, V., and Woeginger, G. 2000. A study of exponential neighborhoods for the traveling salesman problem and the quadratic assignment problem. Math. Prog., Ser. A 87, 519--542.
• 6: Glover, F., and Punnen, A. 1997. The travelling salesman problem: New solvable cases and linkages with the development of new approximation algorithms. J. Oper. Res. Soc. 48, 502--510.
• 7: Gregory Gutin , Alek Vainshtein , Anders Yeo, Domination analysis of combinatorial optimization problems, Discrete Applied Mathematics, v.129 n.2-3, p.513-520, 01 August 2003 [doi>10.1016/S0166-218X(03)00359-7]
• 8: Gutin, G., and Yeo, A. 2001. TSP tour domination and hamilton cycle decompositions of regular digraphs. Oper. Res. Lett. 28, 3, 107--111.
• 9: Gregory Gutin , Anders Yeo, Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number, Discrete Applied Mathematics, v.119 n.1-2, p.107-116, June 15, 2002 [doi>10.1016/S0166-218X(01)00267-0]
• 10: Gutin, G., Yeo, A., and Zverovich, A. 2002a. Exponential neighborhoods and domination analysis for the TSP. In The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen, Eds. Kluwer Academic Publishers, Boston, Chapter 6, 223--256.
• 11: Gutin, G., Yeo, A., and Zverovich, A. 2002b. Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP. Disc. Appl. Math. 117, 1--3, 81--86.
• 12: Refael Hassin , Samir Khuller, z-Approximations, Journal of Algorithms, v.41 n.2, p.429-442, November 2001 [doi>10.1006/jagm.2001.1187]
• 13: Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
• 14: Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
• 15: Phan, V., Skiena, S., and Sumazin, P. 2003. A model for analyzing black-box optimization. In Lecture Notes in Computer Science, vol. 2748. Springer-Verlag, New York, pp. 424--438.
• 16: Punnen, A., Margot, F., and Kabadi, S. 2001. TSP heuristics: Domination analysis and complexity. Res. rep. 2001-06, Dept. of Mathematics, Univ. Kentucky, Mar.
• 17: Rublineckii, V. 1973. Estimates of the accuracy of procedures in the traveling salesman problem. Num. Math. Comput. Tech. (in Russian) 4, 18--23.
• 18: Sarvanov, V., and Doroshko, N. 1981a. The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of exponential cardinality in quadratic time. Softw.: Algor. Prog. (in Russian) 31, 8--11.
• 19: Sarvanov, V., and Doroshko, N. 1981b. The approximate solution of the traveling salesman problem by a local algorithm that searches neighborhoods of factorial cardinality in cubic time. Soft.: Algor. Prog. (in Russian) 31, 11--13.
• 20: Sperner, E. 1928. Ein satzber untermegen einer endlichen menge. Math. Zeitschr. 27, 285--286.
• 21: Valient, L. 1979. The complexity of computing the permanent. Theoret. Comput. Sci. 8, 189--201.
• 22: Zemel, E. 1981. Measuring the quality of approximate solutions to zero-one programming problems. Math. Oper. Res. 6, 319--332.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Performance, Theory

Keywords:
Computation complexity, algorithms analysis, approximation algorithms, dominance analysis