Defying hardness with a hybrid approach

Abstract: "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 hΓéü is efficient but approximately solves instances, whereas hΓéé exactly solves instances but takes superpolynomial time. We present hybrid algorithms for several interesting problems II with a 'hardness-defying' property: there is a set of complexity measures [m[subscript i]] whereby II is conjectured or known to be hard (or unsolvable) for each m[subscript i], but for each heuristic h[subscript i] of the hybrid algorithm, one can give a complexity guarantee for h[subscript i] on the instances of II that S selects for h[subscript i] that is strictly better than m[subscript i]. 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 [not equal to] NP).