{'fraction_non_alphanumeric': 0.10276338514680483, 'fraction_numerical': 0.011226252158894647, 'mean_word_length': 4.545454545454546, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 28, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes

The MAXIMUM INDEPENDENT SET problem in <i>d</i>-box graphs, i.e., in the intersection graphs of axis-parallel rectangles in R<sup><i>d</i></sup>, is a challenge open problem. For any fixed <i>d</i> ≥ 2 the problem is NP-hard and no approximation algorithm with ratio <i>o</i>(log<i><sup>d</sup></i>-<sup>1</sup> <i>n</i>) is known. In some restricted cases, e.g., for <i>d</i>-boxes with bounded aspect ratio, a PTAS exists [17]. In this paper we prove APX-hardness (and hence non-existence of a PTAS, unless P = NP), of the MAXIMUM INDEPENDENT SET problem in <i>d</i>-box graphs for any fixed <i>d</i> ≥ 3. We state also first explicit lower bound 443/442 on efficient approximability in such case. Additionally, we provide a generic method how to prove APX-hardness for many NP-hard graph optimization problems in <i>d</i>-box graphs for any fixed <i>d</i> ≥ 3. In 2-dimensional case we give a generic approach to NP-hardness results for these problems in highly restricted intersection graphs of axis-parallel unit squares (alternatively, in unit disk graphs).