Approximation hardness for small occurrence instances of NP-hard problems

Chlebík, Miroslav and Chlebíková, Janka (2003) Approximation hardness for small occurrence instances of NP-hard problems. In: 5th Italian Conference on Algorithms and Complexity, Rome, 28-30 May 2003.

Full text not available from this repository.


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-3-DM within 139/138 even on instances with exactly two occurrences of each element. Previous known hardness results for bounded occurence case of the problem required that the bound is at least three, and even then no explicit lower bound was known. New structural results which improve the known bounds for 3-regular amplifiers and hence the inapproximability results for numerous small occurrence problems studied earlier by Berman and Karpinski are also presented.

Item Type: Conference or Workshop Item (Paper)
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Depositing User: Miroslav Chlebik
Date Deposited: 06 Feb 2012 19:16
Last Modified: 04 Apr 2012 08:22
📧 Request an update