Confronting hardness using a hybrid approach

ABSTRACT

A hybrid algorithm is a collection of heuristics, paired with a polynomial time selector S that runs on the input to decide which heuristic should be executed to solve the problem. Hybrid algorithms are of particular interest in scenarios where the selector must decide between heuristics that are "good" with respect to different complexity measures.We focus on hybrid algorithms with a "hardness-defying" property: for a problem II, there is a set of complexity measures {mi} whereby II is known or conjectured to be unsolvable for each mi, but for each heuristic hi of the hybrid algorithm, one can give a complexity guarantee for hi on the instances of II that S selects for hi that is strictly better than mi. More concretely, we show that for several NP-hard problems, a given instance can either be solved exactly with substantially improved runtime (e.g. 2^o(n)), or be approximated in polynomial time with an approximation ratio exceeding that of the known or conjectured inapproximability of the problem, assuming P ≠ NP.

REFERENCES

• 1: Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995 [doi>10.1145/210332.210337]
• 2: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 3: Brenda S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of the ACM (JACM), v.41 n.1, p.153-180, Jan. 1994 [doi>10.1145/174644.174650]
• 4: Richard Bellman, Dynamic Programming Treatment of the Travelling Salesman Problem, Journal of the ACM (JACM), v.9 n.1, p.61-63, Jan. 1962 [doi>10.1145/321105.321111]
• 5: Avrim Blum , Goran Konjevod , R. Ravi , Santosh Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoretical Computer Science, v.235 n.1, p.25-42, March 17, 2000 [doi>10.1016/S0304-3975(99)00181-4]
• 6: Hans L. Bodlaender, On linear time minor tests with depth-first search, Journal of Algorithms, v.14 n.1, p.1-23, Jan. 1993 [doi>10.1006/jagm.1993.1001]
• 7: Hans L. Bodlaender , Michael R. Fellows , Michael T. Hallett, Beyond NP-completeness for problems of bounded width (extended abstract): hardness for the W hierarchy, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.449-458, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195229]
• 8: Liming Cai , David Juedes, On the existence of subexponential parameterized algorithms, Journal of Computer and System Sciences, v.67 n.4, p.789-807, December 2003 [doi>10.1016/S0022-0000(03)00074-6]
• 9: Jianer Chen , Xiuzhen Huang , Iyad A. Kanj , Ge Xia, Linear FPT reductions and computational lower bounds, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007391]
• 10: E. Dantsin, M. Gavrilovich, E. A. Hirsch, and B. Konev. MAX SAT approximation beyond the limits of polynomial-time approximation. Annals of Pure and Applied Logic, 113(1--3):81--94, 2001.
• 11: R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer, 1999.
• 12: W. R. Dyksen and C. R. Gritter. Scientific computing and the algorithm selection problem. Expert Systems for Scientific Computing, pages 19--31, 1992.
• 13: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 14: Uriel Feige, Coping with the NP-Hardness of the Graph Bandwidth Problem, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.10-19, July 05-07, 2000
• 15: U. Feige and K. Talwar. Approximating the bandwidth of caterpillars. In RANDOM-APPROX, pages 62--73, 2005.
• 16: Harold N. Gabow, Finding paths and cycles of superpolylogarithmic length, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007418]
• 17: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 18: Carla P. Gomes , Bart Selman, Algorithm portfolios, Artificial Intelligence, v.126 n.1-2, p.43-62, Feb., 2001 [doi>10.1016/S0004-3702(00)00081-3]
• 19: Arvind Gupta , Naomi Nishimura, Sequential and Parallel Algorithms for Embedding Problems on Classes of Partial k-Trees, Proceedings of the 4th Scandinavian Workshop on Algorithm Theory, p.172-182, July 06-08, 1994
• 20: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 21: Johan Håstad , S. Venkatesh, On the advantage over a random assignment, Random Structures & Algorithms, v.25 n.2, p.117-149, September 2004 [doi>10.1002/rsa.20031]
• 22: M. Held and R. M. Karp. A dynamic programming approach to sequencing problems. J. of the Society of Industrial and Applied Mathematics, 10:196--210, 1962.
• 23: E. A. Hirsch. A fast deterministic algorithm for formulas that have many satisfying assignments. Logic Jour. of the IGPL, 6(1):59--71, 1998.
• 24: Edward A. Hirsch, Worst-case study of local search for MAX-k-SAT, Discrete Applied Mathematics, v.130 n.2, p.173-184, 15 August 2003 [doi>10.1016/S0166-218X(02)00404-3]
• 25: Russell Impagliazzo , Ramamohan Paturi , Francis Zane, Which problems have strongly exponential complexity?, Journal of Computer and System Sciences, v.63 n.4, p.512-530, December 2001 [doi>10.1006/jcss.2001.1774]
• 26: M. Jerrum and U. V. Vazirani. A mildly exponential approximation algorithm for the permanent. Algorithmica, 16(3):392--401, 1996.
• 27: Ming-Yang Kao , Yuan Ma , Michael Sipser , Yiqun Yin, Optimal constructions of hybrid algorithms, Journal of Algorithms, v.29 n.1, p.142-164, Oct. 1998 [doi>10.1006/jagm.1998.0959]
• 28: D. R. Karger, R. Motwani, and G. D. S. Ramkumar. On approximating the longest path in a graph. Algorithmica, 18(1):82--98, 1997.
• 29: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O'Donnell, Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.146-154, October 17-19, 2004 [doi>10.1109/FOCS.2004.49]
• 30: Robert Krauthgamer , James R. Lee , Manor Mendel , Assaf Naor, Measured Descent: A New Embedding Method for Finite Metrics, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.434-443, October 17-19, 2004 [doi>10.1109/FOCS.2004.41]
• 31: K. Leyton-Brown, E. Nudelman, G. Andrew, J. McFadden, and Y. Shoham. Boosting as a metaphor for algorithm design. In Principles and Practice of Constraint Programming, pages 899--903, 2003.
• 32: A. Lingas and M. Wahlen. On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems. Electronic Colloquium on Comput. Complexity, 11(39), 2004.
• 33: Serge Plotkin , Satish Rao , Warren D. Smith, Shallow excluded minors and improved graph decompositions, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.462-470, January 23-25, 1994, Arlington, Virginia, United States
• 34: J. R. Rice. The algorithm selection problem. Advances in Computers, 15:65--118, 1976.
• 35: Sartaj Sahni , Teofilo Gonzalez, P-Complete Approximation Problems, Journal of the ACM (JACM), v.23 n.3, p.555-565, July 1976 [doi>10.1145/321958.321975]
• 36: J. B. Saxe. Dynamic programming algorithms for recognizing small bandwidth graphs in polynomial time. SIAM J. on Algebraic and Discr. Methods, 1(4):363--369, 1980.
• 37: A. D. Scott and G. B. Sorkin. Faster algorithms for max cut and max csp, with polynomial expected time for sparse instances. In RANDOM-APPROX, pages 382--395, 2003.
• 38: V. Vassilevska, R. Williams, and S. L. M. Woo. Confronting hardness using a hybrid approach. Technical report, Computer Science Department, Carnegie Mellon University, April 2005. CMU-CS-05-125.
• 39: R. Williams. A new algorithm for optimal constraint satisfaction and its applications. Electronic Colloquium on Comput. Complexity, 11(32), 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

General Terms:
Algorithms, Theory