
CMUCS04159
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS04159
Defying Hardness With a Hybrid Approach
Ryan Williams
August 2004
CMUCS04159.ps
CMUCS04159.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
"hardnessdefying" 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 NPhard 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
