Under the auspices of the Computational Complexity Foundation (CCF)
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.