CMU-CS-05-125
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-05-125

Confronting Hardness Using A Hybrid Approach

Virginia Vassilevska, Ryan Williams, Shan Leung Maverick Woo

April 2005

CMU-CS-05-125.ps
CMU-CS-05-125.pdf


Keywords: Hybrid algorithms, approximation algorithms, sub-exponential time algorithms, combinatorial optimization


A hybrid algorithm is a collection of heuristics, paired with a polynomial time selector S that runs on the input to decide which heuristic should be executed to solve the problem. Hybrid algorithms are interesting in scenarios where the selector must decide between heuristics that are "good" with respect to different complexity measures.

In this paper, we focus on hybrid algorithms with a "hardness-defying" property: for a problem Pi, there is a set of complexity measures {mi} whereby Pi is known or conjectured 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 Pi that S selects for hi that is strictly better than mi. For example, we show that for NP-hard problems such as Max-Ek-Lin-p, Longest Path and Minimum Bandwidth, a given instance can either be solved exactly in ``sub-exponential'' (2o(n)) time, or be approximated in polynomial time with an approximation ratio exceeding that of the known or conjectured inapproximability of the problem, assuming P != NP. We also prove some inherent limitations to the design of hybrid algorithms that arise under the assumption that NP requires exponential time algorithms.

35 pages


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

This page maintained by reports@cs.cmu.edu