Inapproximability results for bounded variants of optimization 	problems

Miroslav Chlebik; Janka Chlebikova

doi:10.1007/978-3-540-45077-1_4

Inapproximability results for bounded variants of optimization problems

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

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

Abstract

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 9594 for Max-3DM, and factor of 4847 for Max-4DM; in both cases the hardness result applies even to instances with exactly two occurrences of each element.

Original language	English
Title of host publication	Fundamentals of computation theory
Subtitle of host publication	14th international symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003. proceedings
Editors	Andrzej Lingas, Bengt J. Nilsson
Place of Publication	Berlin
Publisher	Springer
Pages	27-38
Volume	2751
ISBN (Electronic)	9783540450771
ISBN (Print)	9783540405436
DOIs	https://doi.org/10.1007/978-3-540-45077-1_4
Publication status	Published - 2003

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2751
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-540-45077-1_4

Cite this

Chlebik, M., & Chlebikova, J. (2003). Inapproximability results for bounded variants of optimization problems. In A. Lingas, & B. J. Nilsson (Eds.), Fundamentals of computation theory : 14th international symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003. proceedings (Vol. 2751, pp. 27-38). (Lecture Notes in Computer Science; Vol. 2751). Springer. https://doi.org/10.1007/978-3-540-45077-1_4

@inproceedings{b6cd2b1f508544e2a9d42dcb98ca0e15,

title = "Inapproximability results for bounded variants of optimization problems",

abstract = "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 9594 for Max-3DM, and factor of 4847 for Max-4DM; in both cases the hardness result applies even to instances with exactly two occurrences of each element.",

author = "Miroslav Chlebik and Janka Chlebikova",

year = "2003",

doi = "10.1007/978-3-540-45077-1_4",

language = "English",

isbn = "9783540405436",

volume = "2751",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "27--38",

editor = "Lingas, {Andrzej } and Nilsson, {Bengt J.}",

booktitle = "Fundamentals of computation theory",

}

Chlebik, M & Chlebikova, J 2003, Inapproximability results for bounded variants of optimization problems. in A Lingas & BJ Nilsson (eds), Fundamentals of computation theory : 14th international symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003. proceedings. vol. 2751, Lecture Notes in Computer Science, vol. 2751, Springer, Berlin, pp. 27-38. https://doi.org/10.1007/978-3-540-45077-1_4

Inapproximability results for bounded variants of optimization problems. / Chlebik, Miroslav; Chlebikova, Janka.
Fundamentals of computation theory : 14th international symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003. proceedings. ed. / Andrzej Lingas; Bengt J. Nilsson. Vol. 2751 Berlin: Springer, 2003. p. 27-38 (Lecture Notes in Computer Science; Vol. 2751).

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

TY - GEN

T1 - Inapproximability results for bounded variants of optimization problems

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

PY - 2003

Y1 - 2003

N2 - 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 9594 for Max-3DM, and factor of 4847 for Max-4DM; in both cases the hardness result applies even to instances with exactly two occurrences of each element.

AB - 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 9594 for Max-3DM, and factor of 4847 for Max-4DM; in both cases the hardness result applies even to instances with exactly two occurrences of each element.

U2 - 10.1007/978-3-540-45077-1_4

DO - 10.1007/978-3-540-45077-1_4

M3 - Conference contribution

SN - 9783540405436

VL - 2751

T3 - Lecture Notes in Computer Science

SP - 27

EP - 38

BT - Fundamentals of computation theory

A2 - Lingas, Andrzej

A2 - Nilsson, Bengt J.

PB - Springer

CY - Berlin

ER -

Chlebik M, Chlebikova J. Inapproximability results for bounded variants of optimization problems. In Lingas A, Nilsson BJ, editors, Fundamentals of computation theory : 14th international symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003. proceedings. Vol. 2751. Berlin: Springer. 2003. p. 27-38. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-45077-1_4

Inapproximability results for bounded variants of optimization problems

Abstract

Publication series

Access to Document

Fingerprint

Cite this