论文标题
参数化近似，最大重量独立的矩形和段集
Parameterized Approximation for Maximum Weight Independent Set of Rectangles and Segments
论文作者
论文摘要
在最大重量独立的矩形问题集（MWISR）中，我们在平面中给出了$ n $ axis-Axis-Axallear矩形的加权集。任务是找到最大可能的总重量的成对非重叠矩形的子集。由于Chalermsook和Walczak（Soda 2021），此问题是NP-HARD和最著名的多项式时间近似算法，可实现近似因子$ O（\ log \ log \ log \ log \ log n）$。尽管在未加权的设置中，由于米切尔（Focs 2021）和Gálvez等人，恒定因子近似算法是已知的。 （SODA 2022），它保持开放，可以将这些技术扩展到加权设置。 在本文中，我们考虑MWISR通过参数化近似的镜头。 Grandoni等。 （ESA 2019）给出了$（1-ε）$ - 近似算法，运行时间$ k^{o（k/ε^8）} n^{o（1/ε^8）} $ time，其中$ k $是最佳解决方案中矩形的数量。不幸的是，它们的算法仅在未加权的设置中起作用，并且将其作为一个开放的问题，可以在加权设置中提供参数化的近似方案。 我们的贡献是对Grandoni等人的公开问题的部分答案。 （ESA 2019）。我们给出了给定参数$ k $的参数化近似算法，找到一组非重叠的重量矩形至少$（1-ε）\ text {opt} _k $ in $ 2^{o（k \ log log（k/ε）} n^n^n^n $（opt）最多$ k $的基数解决方案的重量。请注意，因此，我们的算法可能返回由$ K $矩形组成的解决方案。 To complement this apparent weakness, we also propose a parameterized approximation scheme with running time $2^{O(k^2 \log(k/ε))} n^{O(1)}$ that finds a solution with cardinality at most $k$ and total weight at least $(1-ε)\text{opt}_k$ for the special case of axis-parallel segments.
In the Maximum Weight Independent Set of Rectangles problem (MWISR) we are given a weighted set of $n$ axis-parallel rectangles in the plane. The task is to find a subset of pairwise non-overlapping rectangles with the maximum possible total weight. This problem is NP-hard and the best-known polynomial-time approximation algorithm, due to by Chalermsook and Walczak (SODA 2021), achieves approximation factor $O(\log\log n )$. While in the unweighted setting, constant factor approximation algorithms are known, due to Mitchell (FOCS 2021) and to Gálvez et al. (SODA 2022), it remains open to extend these techniques to the weighted setting. In this paper, we consider MWISR through the lens of parameterized approximation. Grandoni et al. (ESA 2019) gave a $(1-ε)$-approximation algorithm with running time $k^{O(k/ε^8)} n^{O(1/ε^8)}$ time, where $k$ is the number of rectangles in an optimum solution. Unfortunately, their algorithm works only in the unweighted setting and they left it as an open problem to give a parameterized approximation scheme in the weighted setting. Our contribution is a partial answer to the open question of Grandoni et al. (ESA 2019). We give a parameterized approximation algorithm for MWISR that given a parameter $k$, finds a set of non-overlapping rectangles of weight at least $(1-ε) \text{opt}_k$ in $2^{O(k \log(k/ε))} n^{O(1/ε)}$ time, where $\text{opt}_k$ is the maximum weight of a solution of cardinality at most $k$. Note that thus, our algorithm may return a solution consisting of more than $k$ rectangles. To complement this apparent weakness, we also propose a parameterized approximation scheme with running time $2^{O(k^2 \log(k/ε))} n^{O(1)}$ that finds a solution with cardinality at most $k$ and total weight at least $(1-ε)\text{opt}_k$ for the special case of axis-parallel segments.
