Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-073 | 12th December 2002 00:00

Approximation Hardness for Small Occurrence Instances of NP-Hard Problem



The paper contributes to the systematic study (started by Berman and
Karpinski) of explicit approximability lower bounds for small occurrence optimization
problems. We present parametrized reductions for some packing and
covering problems, including 3-Dimensional Matching, and prove the best
known inapproximability results even for highly restricted versions of
them. For example, we show that it is NP-hard to approximate Max-3DM
within 141/140 even on instances with exactly two occurrences of each

Our reductions from Max-E3-Lin-2 depend on parameters of amplifiers
that provably exist, we need not restrict ourselves to amplifiers that
can be constructed efficiently. New structural results which improve the
known bounds for 3-regular amplifiers and hence the inapproximability
results for numerous small occurrence problems studied by Berman and
Karpinski in the article ``On some tighter inapproximability results''
(ECC/65, 1998) are also presented.

ISSN 1433-8092 | Imprint