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