Defying Hardness With a Hybrid Approach

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 {mi} 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 � = NP)