File(s) not publicly available
The complexity of combinatorial optimization problems on d-dimensional boxes
journal contribution
posted on 2023-06-08, 09:42 authored by Miroslav ChlebikMiroslav Chlebik, Janka ChlebíkováThe Maximum Independent Set problem in d-box graphs, i.e., in intersection graphs of axis-parallel rectangles in R-d, is known to be NP-hard for any fixed d >= 2. A challenging open problem is that of how closely the solution can be approximated by a polynomial time algorithm. For the restricted case of d-boxes with bounded aspect ratio a PTAS exists [T. Erlebach, K. Jansen, and E. Seidel, SIAM J. Comput., 34 (2005), pp. 1302-1323]. In the general case no polynomial time algorithm with approximation ratio o(log(d-1)n) for a set of n d-boxes is known. In this paper we prove APX-hardness of the MAXIMUM INDEPENDENT SET problem in d-box graphs for any fixed d >= 3. We give an explicit lower bound 245/244 on efficient approximability for this problem unless P = NP. Additionally, we provide a generic method how to prove APX-hardness for other graph optimization problems in d-box graphs for any fixed d >= 3.
History
Publication status
- Published
Journal
SIAM Journal on Discrete MathematicsISSN
0895-4801External DOI
Issue
1Volume
21Page range
158-169Pages
12.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