University of Sussex
Browse

File(s) not publicly available

Approximation hardness for small occurrence instances of NP-hard problems

presentation
posted on 2023-06-07, 22:25 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková
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.

History

Publication status

  • Published

ISSN

0302-9743

Publisher

Springer, Berlin, ALLEMAGNE (2003) (Monographie)

Volume

LNCS 2

Pages

13.0

Presentation Type

  • paper

Event name

5th Italian Conference on Algorithms and Complexity

Event location

Rome, 28-30 May 2003

Event type

conference

ISBN

3-540-40176-8

Department affiliated with

  • Mathematics Publications

Notes

ALGORITHMS AND COMPLEXITY, PROCEEDINGS

Full text available

  • No

Peer reviewed?

  • Yes

Editors

R Silvestri, R Petreschi, G Persiano

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC