The complexity of combinatorial optimization problems on d‐dimensional boxes

Miroslav Chlebik, Janka Chlebikova

Research output: Contribution to journalArticlepeer-review

140 Downloads (Pure)

Abstract

The Maximum Independent Set problem in d-box graphs, i.e., in intersection graphs of axis-parallel rectangles in Rd, 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.
Original languageEnglish
Pages (from-to)158-169
Number of pages12
JournalSiam Journal on Discrete Mathematics
Volume21
Issue number1
DOIs
Publication statusPublished - 2007

Keywords

  • independent set
  • geometric intersection graphs
  • rectangle graphs

Fingerprint

Dive into the research topics of 'The complexity of combinatorial optimization problems on d‐dimensional boxes'. Together they form a unique fingerprint.

Cite this