Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NP-HARD COMBINATORIAL OPTIMIZATION PROBLEMS:
Reports tagged with NP-hard combinatorial optimization problems:
TR02-073 | 12th December 2002
Janka Chlebíková, Miroslav Chlebik

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 ... more >>>




ISSN 1433-8092 | Imprint