Complexity of approximating bounded variants of 		optimization problems

Miroslav Chlebik; Janka Chlebikova

doi:doi:10.1016/j.tcs.2005.11.029

Complexity of approximating bounded variants of optimization problems

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

Research output: Contribution to journal › Article › peer-review

224 Downloads (Pure)

Abstract

We study low degree graph problems such as \textsc{Maximum
Independent Set} and \textsc{Minimum Vertex Cover}. The goal is to improve approximation lower bounds for them and for a number of related problems like Max-B-Set Packing, Min-B-Set Cover, and Max-B-Dimensional Matching, B>= 3. We prove, for example, that it is NP-hard to achieve an approximation factor of 95/94 for Max-3-DM, and a factor of 48/47 for Max-4-DM. In both cases the hardness result applies even to instances with exactly two occurrences of each element.

Original language	English
Pages (from-to)	320-338
Journal	Theoretical Computer Science
Volume	354
Issue number	3
DOIs	https://doi.org/doi:10.1016/j.tcs.2005.11.029
Publication status	Published - 4 Apr 2006

Access to Document

doi:10.1016/j.tcs.2005.11.029

3DM_JOURNAL_revision_old
“NOTICE: this is the author’s version of a work that was accepted for publication in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical Computer Science, [VOL354, ISSUE3, (4/4/2006)] DOI10.1016/j.tcs.2005.11.029¨
Accepted author manuscript (Post-print), 293 KB

Cite this

@article{033531e7202b476c8568b9c586a2a819,

title = "Complexity of approximating bounded variants of optimization problems",

abstract = "We study low degree graph problems such as \textsc{Maximum Independent Set} and \textsc{Minimum Vertex Cover}. The goal is to improve approximation lower bounds for them and for a number of related problems like Max-B-Set Packing, Min-B-Set Cover, and Max-B-Dimensional Matching, B>= 3. We prove, for example, that it is NP-hard to achieve an approximation factor of 95/94 for Max-3-DM, and a factor of 48/47 for Max-4-DM. In both cases the hardness result applies even to instances with exactly two occurrences of each element.",

author = "Miroslav Chlebik and Janka Chlebikova",

note = "“NOTICE: this is the author{\textquoteright}s version of a work that was accepted for publication in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical Computer Science, [VOL354, ISSUE3, (4/4/2006)] DOI10.1016/j.tcs.2005.11.029€¨",

year = "2006",

month = apr,

day = "4",

doi = "doi:10.1016/j.tcs.2005.11.029",

language = "English",

volume = "354",

pages = "320--338",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Complexity of approximating bounded variants of optimization problems

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

N1 - “NOTICE: this is the author’s version of a work that was accepted for publication in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical Computer Science, [VOL354, ISSUE3, (4/4/2006)] DOI10.1016/j.tcs.2005.11.029€¨

PY - 2006/4/4

Y1 - 2006/4/4

N2 - We study low degree graph problems such as \textsc{Maximum Independent Set} and \textsc{Minimum Vertex Cover}. The goal is to improve approximation lower bounds for them and for a number of related problems like Max-B-Set Packing, Min-B-Set Cover, and Max-B-Dimensional Matching, B>= 3. We prove, for example, that it is NP-hard to achieve an approximation factor of 95/94 for Max-3-DM, and a factor of 48/47 for Max-4-DM. In both cases the hardness result applies even to instances with exactly two occurrences of each element.

AB - We study low degree graph problems such as \textsc{Maximum Independent Set} and \textsc{Minimum Vertex Cover}. The goal is to improve approximation lower bounds for them and for a number of related problems like Max-B-Set Packing, Min-B-Set Cover, and Max-B-Dimensional Matching, B>= 3. We prove, for example, that it is NP-hard to achieve an approximation factor of 95/94 for Max-3-DM, and a factor of 48/47 for Max-4-DM. In both cases the hardness result applies even to instances with exactly two occurrences of each element.

U2 - doi:10.1016/j.tcs.2005.11.029

DO - doi:10.1016/j.tcs.2005.11.029

M3 - Article

SN - 0304-3975

VL - 354

SP - 320

EP - 338

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -

Complexity of approximating bounded variants of optimization problems

Abstract

Access to Document

Fingerprint

Cite this