Approximation hardness for small occurrence instances of NP-hard problems

Miroslav Chlebik; Janka Chlebikova

doi:10.1007/3-540-44849-7_21

Approximation hardness for small occurrence instances of NP-hard problems

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

311 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 language	English
Title of host publication	Algorithms and complexity
Subtitle of host publication	5th Italian conference, CIAC 2003, Rome, Italy, May 28–30, 2003. proceedings
Editors	Rossella Petreschi, Giuseppe Persiano, Riccardo Silvestri
Place of Publication	Berlin
Publisher	Springer
Pages	152-164
Volume	2653
ISBN (Electronic)	9783540448495
ISBN (Print)	9783540401766
DOIs	https://doi.org/10.1007/3-540-44849-7_21
Publication status	Published - 2003

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2653
ISSN (Print)	0302-9743

Access to Document

10.1007/3-540-44849-7_21

Small Occurrence post-print
The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-44849-7_21.
Accepted author manuscript (Post-print), 170 KB

Cite this

Chlebik, M., & Chlebikova, J. (2003). Approximation hardness for small occurrence instances of NP-hard problems. In R. Petreschi, G. Persiano, & R. Silvestri (Eds.), Algorithms and complexity : 5th Italian conference, CIAC 2003, Rome, Italy, May 28–30, 2003. proceedings (Vol. 2653, pp. 152-164). (Lecture Notes in Computer Science; Vol. 2653). Springer. https://doi.org/10.1007/3-540-44849-7_21

Chlebik, Miroslav ; Chlebikova, Janka. / Approximation hardness for small occurrence instances of NP-hard problems. Algorithms and complexity : 5th Italian conference, CIAC 2003, Rome, Italy, May 28–30, 2003. proceedings. editor / Rossella Petreschi ; Giuseppe Persiano ; Riccardo Silvestri. Vol. 2653 Berlin : Springer, 2003. pp. 152-164 (Lecture Notes in Computer Science).

@inproceedings{fe0d8e3c740b4b8499624a0b05cc6f6b,

title = "Approximation hardness for small occurrence instances of NP-hard problems",

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.",

author = "Miroslav Chlebik and Janka Chlebikova",

note = "“The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-44849-7_21”.",

year = "2003",

doi = "10.1007/3-540-44849-7_21",

language = "English",

isbn = "9783540401766",

volume = "2653",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "152--164",

editor = "Rossella Petreschi and Giuseppe Persiano and Silvestri, {Riccardo }",

booktitle = "Algorithms and complexity",

}

Chlebik, M & Chlebikova, J 2003, Approximation hardness for small occurrence instances of NP-hard problems. in R Petreschi, G Persiano & R Silvestri (eds), Algorithms and complexity : 5th Italian conference, CIAC 2003, Rome, Italy, May 28–30, 2003. proceedings. vol. 2653, Lecture Notes in Computer Science, vol. 2653, Springer, Berlin, pp. 152-164. https://doi.org/10.1007/3-540-44849-7_21

Approximation hardness for small occurrence instances of NP-hard problems. / Chlebik, Miroslav; Chlebikova, Janka.
Algorithms and complexity : 5th Italian conference, CIAC 2003, Rome, Italy, May 28–30, 2003. proceedings. ed. / Rossella Petreschi; Giuseppe Persiano; Riccardo Silvestri. Vol. 2653 Berlin: Springer, 2003. p. 152-164 (Lecture Notes in Computer Science; Vol. 2653).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approximation hardness for small occurrence instances of NP-hard problems

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

N1 - “The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-44849-7_21”.

PY - 2003

Y1 - 2003

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

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

U2 - 10.1007/3-540-44849-7_21

DO - 10.1007/3-540-44849-7_21

M3 - Conference contribution

SN - 9783540401766

VL - 2653

T3 - Lecture Notes in Computer Science

SP - 152

EP - 164

BT - Algorithms and complexity

A2 - Petreschi, Rossella

A2 - Persiano, Giuseppe

A2 - Silvestri, Riccardo

PB - Springer

CY - Berlin

ER -

Chlebik M, Chlebikova J. Approximation hardness for small occurrence instances of NP-hard problems. In Petreschi R, Persiano G, Silvestri R, editors, Algorithms and complexity : 5th Italian conference, CIAC 2003, Rome, Italy, May 28–30, 2003. proceedings. Vol. 2653. Berlin: Springer. 2003. p. 152-164. (Lecture Notes in Computer Science). doi: 10.1007/3-540-44849-7_21

Approximation hardness for small occurrence instances of NP-hard problems

Abstract

Publication series

Access to Document

Fingerprint

Cite this