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-9743Publisher
Springer, Berlin, ALLEMAGNE (1973) (Revue)Volume
LNCS 2Pages
12.0Presentation Type
- paper
Event name
14th International Symposium on Fundamentals of Computation TheoryEvent location
MALMO, SWEDENEvent type
conferenceISBN
3-540-40543-7Department affiliated with
- Mathematics Publications
Full text available
- No
Peer reviewed?
- Yes
Editors
BJ Nilsson, A LingasLegacy Posted Date
2012-02-06Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC