University of Sussex
Browse

File(s) not publicly available

Inapproximability results for bounded variants of optimization problems

presentation
posted on 2023-06-08, 08:31 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková
We study small degree graph problems such as MAXIMUM INDEPENDENT SET and MINIMUM NODE COVER and improve approximation lower bounds for them and for a number of related problems, like MAX-B-SET PACKING, MIN-B-SET COVER, MAX-MATCHING in B-uniform 2-regular hypergraphs. For example, we prove NP-hardness factor of 95/94 for MAX-3DM, and factor of 48/47 for MAX-4DM; in both cases the hardness result applies even to instances with exactly two occurrences of each element.

History

Publication status

  • Published

ISSN

0302-9743

Publisher

Springer, Berlin, ALLEMAGNE (1973) (Revue)

Volume

LNCS 2

Pages

12.0

Presentation Type

  • paper

Event name

14th International Symposium on Fundamentals of Computation Theory

Event location

MALMO, SWEDEN

Event type

conference

ISBN

3-540-40543-7

Department affiliated with

  • Mathematics Publications

Full text available

  • No

Peer reviewed?

  • Yes

Editors

BJ Nilsson, A Lingas

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