File(s) not publicly available
Complexity of approximating bounded variants of optimization problems
journal contribution
posted on 2023-06-07, 21:45 authored by Miroslav ChlebikMiroslav Chlebik, Janka ChlebíkováWe study low degree graph problems such as Maximum Independent Set and 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, B3. We prove, for example, that it is NP-hard to achieve an approximation factor of for Max-3-DM, and a factor of for Max-4-DM. In both cases the hardness result applies even to instances with exactly two occurrences of each element.
History
Publication status
- Published
Journal
Theoretical Computer ScienceISSN
0304-3975External DOI
Issue
3Volume
354Page range
320-338Pages
19.0Department affiliated with
- Mathematics Publications
Full text available
- No
Peer reviewed?
- Yes
Legacy Posted Date
2012-02-06Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC