Defying hardness with a hybrid approach
Defying hardness with a hybrid approach
复制标题
通过混合方法克服困难
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Ryan Williams
中科院分区：
文献类型：
--
作者：
Ryan Williams
混合算法是一个启发式算法的集合，与一个多项式时间过程S（称为选择器）配对，该过程基于对输入的初步扫描来决定应该执行哪个启发式算法。我们调查的情况下，选择器必须决定之间的启发式是“好”的相对于不同的复杂性措施，例如启发式H1是有效的，但近似解决的实例，而H2精确解决的实例，但需要超多项式时间。我们提出了几个有趣的问题的混合算法与“硬度蔑视”的属性：有一组的复杂性措施{米}，其中，对于每一个米，证明或已知的是硬（或不可解），但对于每个启发式喜的混合算法，可以给一个复杂性保证喜的实例S选择的喜是严格优于米。例如，一些NP难问题允许一个混合算法，给定一个实例，可以在“次指数”时间内精确求解，或者在多时间内近似求解，其性能比超过问题的已知不可近似性（在P 6= NP下）。作者部分得到了NSF研究生研究奖学金和NSF ALADDIN中心的资助，资助号为0122581。
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 6= NP). The author was supported in part by an NSF Graduate Research Fellowship, and the NSF ALADDIN Center under Grant No. 0122581.