  We study optimization problems that are neither approximable in polynomial
time (at least with a constant factor) nor fixed parameter tractable, under
widely believed complexity assumptions. Specifically, we focus on Maximum
Independent Set, Vertex Coloring, Set Cover, and Bandwidth.
  In recent years, many researchers design exact exponential-time algorithms
for these and other hard problems. The goal is getting the time complexity
still of order $O(c^n)$, but with the constant $c$ as small as possible. In
this work we extend this line of research and we investigate whether the
constant $c$ can be made even smaller when one allows constant factor
approximation. In fact, we describe a kind of approximation schemes --
trade-offs between approximation factor and the time complexity.
  We study two natural approaches. The first approach consists of designing a
backtracking algorithm with a small search tree. We present one result of that
kind: a $(4r-1)$-approximation of Bandwidth in time $O^*(2^{n/r})$, for any
positive integer $r$.
  The second approach uses general transformations from exponential-time exact
algorithms to approximations that are faster but still exponential-time. For
example, we show that for any reduction rate $r$, one can transform any
$O^*(c^n)$-time algorithm for Set Cover into a $(1+\ln r)$-approximation
algorithm running in time $O^*(c^{n/r})$. We believe that results of that kind
extend the applicability of exact algorithms for NP-hard problems.
