## January 22, Winter Quarter 2010: Theory Seminar

### 1:00pm in 1423 Bren Hall

#
Paired Approximation Problems and Incompatible Inapproximabilities

## David Eppstein, UC Irvine

Presenting his paper from SODA 2010

Abstract: 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.