CMU-CS-05-125Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-05-125
Virginia Vassilevska, Ryan Williams, Shan Leung Maverick Woo April 2005
CMU-CS-05-125.ps
Keywords: Hybrid algorithms, approximation algorithms,
sub-exponential time algorithms, combinatorial optimization
In this paper, we focus on hybrid algorithms with a "hardness-defying"
property: for a problem Pi is known or conjectured to be hard
(or unsolvable) for each m , but for each
heuristic _{i}h of the hybrid algorithm, one
can give a complexity guarantee for _{i}h _{i}on the
instances of Pi that S selects for h that is
_{i}strictly better than m. 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''
(2_{i}^{o(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 This page maintained by reports@cs.cmu.edu |