Approximation hardness for small occurrence instances of NP-hard problems

Miroslav Chlebik, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

191 Downloads (Pure)

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-3-DM within TeX 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.
Original languageEnglish
Title of host publicationAlgorithms and complexity
Subtitle of host publication5th Italian conference, CIAC 2003, Rome, Italy, May 28–30, 2003. proceedings
EditorsRossella Petreschi, Giuseppe Persiano, Riccardo Silvestri
Place of PublicationBerlin
PublisherSpringer
Pages152-164
Volume2653
ISBN (Electronic)9783540448495
ISBN (Print)9783540401766
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2653
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Approximation hardness for small occurrence instances of NP-hard problems'. Together they form a unique fingerprint.

Cite this