CMU-CS-04-159
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-04-159

Defying Hardness With a Hybrid Approach

Ryan Williams

August 2004

CMU-CS-04-159.ps
CMU-CS-04-159.pdf


Keywords: Approximation, exact algorithms, hybrid algorithms, algorithm selection, complexity


A hybrid algorithm is a collection of heuristics, paired with a polynomial time procedure S (called a selector) that decides based on a preliminary scan of the input which heuristic should be executed. We investigate scenarios where the selector must decide between heuristics that are "good" with respect to different complexity measures, e.g. heuristic h1 is efficient but approximately solves instances, whereas h2 exactly solves instances but takes superpolynomial time. We present hybrid algorithms for several interesting problems with a "hardness-defying" property: there is a set of complexity measures f mi g whereby is conjectured or known to be hard (or 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 that S selects for hi that is strictly better than mi. For example, some NP-hard problems admit a hybrid algorithm that given an instance can either solve it exactly in 'subexponential" time, or approximately solve it in polytime with a performance ratio exceeding that of the known inapproximability of the problem (under P 6 = NP).

21 pages


Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu