This paper considers pairs of optimization problems that are defined from a
single input and for which it is desired to find a good approximation to either
one of the problems. In many instances, it is possible to efficiently find an
approximation of this type that is better than known inapproximability lower
bounds for either of the two individual optimization problems forming the pair.
In particular, we find either a $(1+\epsilon)$-approximation to $(1,2)$-TSP or
a $1/\epsilon$-approximation to maximum independent set, from a given graph, in
linear time. We show a similar paired approximation result for finding either a
coloring or a long path. However, no such tradeoff exists in some other cases:
for set cover and hitting set problems defined from a single set family, and
for clique and independent set problems on the same graph, it is not possible
to find an approximation when both problems are combined that is better than
the best approximation for either problem on its own.