pith. sign in

arxiv: 1906.10982 · v1 · pith:ZWZEYFCLnew · submitted 2019-06-26 · 💻 cs.DS

Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack

Fabrizio Grandoni , Stefan Kratsch , Andreas Wiese This is my paper

Pith reviewed 2026-05-25 15:23 UTC · model grok-4.3

classification 💻 cs.DS
keywords parameterized approximationindependent set of rectanglesgeometric knapsackW[1]-hardnessapproximation schemeMISRTDKR
0
0 comments X

The pith

Parameterized approximation schemes exist for maximum independent set of rectangles and geometric knapsack with rotations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes parameterized approximation schemes for the maximum independent set of rectangles problem and for the two-dimensional geometric knapsack problem allowing 90-degree rotations. For any constant eps greater than zero and any integer k, the algorithms run in time f(k, eps) n raised to a power depending only on eps. They either return a feasible solution of size at least k over 1 plus eps, or correctly report that the optimum solution has size less than k. The results matter because both problems are NP-hard and W[1]-hard, and the schemes provide a way to obtain arbitrarily good approximations when the target solution size k is treated as the parameter.

Core claim

We present a parameterized approximation scheme for MISR: for any eps greater than zero and integer k greater than zero, in time f(k, eps) n to the g(eps), either output a solution of size at least k divided by 1 plus eps or declare that the optimum solution has size less than k. We show that both TDK and TDKR are W[1]-hard, and we present a PAS for TDKR. For all considered problems, an algorithm with time f(k, eps) n to the O(1) would yield an FPT exact algorithm by setting eps to 1 over k plus 1, contradicting the W[1]-hardness.

What carries the argument

The parameterized approximation scheme (PAS) that, for parameters eps and k, either produces a solution of value at least k divided by 1 plus eps or decides the optimum lies below k, with runtime f(k, eps) n to a power depending on eps.

If this is right

  • MISR admits a PAS with the stated runtime and guarantee.
  • TDKR admits a PAS with the stated runtime and guarantee.
  • Both TDK and TDKR are W[1]-hard parameterized by solution size.
  • No PAS with runtime f(k, eps) n to the O(1) can exist for these problems unless FPT equals W[1].

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The allowance for the polynomial exponent to depend on eps may transfer to other geometric selection problems that already possess a QPTAS.
  • When k is moderate, the PAS can deliver better practical approximations than the known O(log log n) polynomial-time factor for MISR.
  • Similar parameterization by solution cardinality could be tested on variants of the problems that include weights or additional constraints.

Load-bearing premise

The exact versions of TDK and TDKR are W[1]-hard when parameterized by the solution size k.

What would settle it

An algorithm solving exact TDKR in time f(k) n to a constant power independent of eps would contradict the W[1]-hardness result shown for that problem.

Figures

Figures reproduced from arXiv: 1906.10982 by Andreas Wiese, Fabrizio Grandoni, Stefan Kratsch.

Figure 2
Figure 2. Figure 2: We place one such rectangle R` between any two consecutive items i`, i`+1. The height of R` equals the vertical distance between i` and i`+1 (at most (1/k) BN) and the width of R` equals (1/k) BN. Since vi` , vi`+1 are connected by an arc in G0 , we can draw a vertical line segment connecting i` with i`+1. We place R` such that it is intersected by this line segment. Note that for the horizontal position o… view at source ↗
Figure 4
Figure 4. Figure 4: We also note that both our PASs work for the cardinality version of the problems: [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
read the original abstract

The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1+eps)-approximations in f(k,eps)n^{O(1)} time where k is some parameter of the input. We obtain the following results on parameterized approximability: 1) In the maximum independent set of rectangles problem (MISR) we are given a collection of n axis parallel rectangles in the plane. Our goal is to select a maximum-cardinality subset of pairwise non-overlapping rectangles. This problem is NP-hard and also W[1]-hard [Marx, ESA'05]. The best-known polynomial-time approximation factor is O(loglog n) [Chalermsook and Chuzhoy, SODA'09] and it admits a QPTAS [Adamaszek and Wiese, FOCS'13; Chuzhoy and Ene, FOCS'16]. Here we present a parameterized approximation scheme (PAS) for MISR, i.e. an algorithm that, for any given constant eps>0 and integer k>0, in time f(k,eps)n^{g(eps)}, either outputs a solution of size at least k/(1+eps), or declares that the optimum solution has size less than k. 2) In the (2-dimensional) geometric knapsack problem (TDK) we are given an axis-aligned square knapsack and a collection of axis-aligned rectangles in the plane (items). Our goal is to translate a maximum cardinality subset of items into the knapsack so that the selected items do not overlap. In the version of TDK with rotations (TDKR), we are allowed to rotate items by 90 degrees. Both variants are NP-hard, and the best-known polynomial-time approximation factors are 558/325+eps and 4/3+eps, resp. [Galvez et al., FOCS'17]. These problems admit a QPTAS for polynomially bounded item sizes [Adamaszek and Wiese, SODA'15]. We show that both variants are W[1]-hard. Furthermore, we present a PAS for TDKR. For all considered problems, getting time f(k,eps)n^{O(1)}, rather than f(k,eps)n^{g(eps)}, would give FPT time f'(k)n^{O(1)} exact algorithms using eps=1/(k+1), contradicting W[1]-hardness.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper claims to establish parameterized approximation schemes (PAS) for Maximum Independent Set of Rectangles (MISR) and 2D Geometric Knapsack with Rotations (TDKR). For any fixed ε>0 and integer k>0 the algorithms run in time f(k,ε)n^{g(ε)}, either returning an independent set (or feasible packing) of size at least k/(1+ε) or correctly declaring that the optimum is smaller than k. It also proves W[1]-hardness of the exact versions of TDK and TDKR, which is used to argue that the n^{g(ε)} dependence cannot be replaced by n^{O(1)} without implying an FPT exact algorithm.

Significance. If correct, the results supply the first PAS results for these two geometric problems, showing that (1+ε)-approximations become FPT in the solution-size parameter k while the exact problems remain W[1]-hard. The hardness statements cleanly separate the PAS from an FPT exact algorithm via the standard ε=1/(k+1) substitution. The work therefore strengthens the known landscape between QPTAS, polynomial-time approximation, and parameterized complexity for rectangle packing problems.

minor comments (3)
  1. §1, paragraph after the MISR definition: the sentence claiming 'the best-known polynomial-time approximation factor is O(log log n)' should cite Chalermsook-Chuzhoy SODA'09 explicitly rather than only in the abstract.
  2. The runtime notation f(k,ε)n^{g(ε)} is used consistently, but the paper never states whether g(ε) is polynomial, exponential, or worse; a single sentence clarifying the dependence would improve readability.
  3. Theorem statements for the PAS algorithms (presumably in §3 and §5) should include the precise form of g(ε) or at least an explicit upper bound on the exponent.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive evaluation of our work. The recommendation for minor revision is appreciated. Since the report lists no specific major comments, we have no points to address point-by-point.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central contributions are the construction of PAS algorithms for MISR and TDKR (with the stated runtime and approximation guarantee) together with independent W[1]-hardness proofs for the exact versions of TDK and TDKR. The standard argument that an f(k,eps)n^{O(1)} PAS would yield an FPT exact algorithm (via eps=1/(k+1)) is a direct logical implication that does not reduce any claim to a fitted parameter, self-definition, or self-citation chain. Hardness results are lower-bound reductions presented as separate theorems; prior QPTAS citations (including self-citations to Wiese) support context but are not load-bearing for the new PAS or hardness statements. No equation or derivation reduces by construction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard definitions from parameterized complexity (W[1]-hardness) and geometric problem statements (axis-aligned rectangles); no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption W[1]-hardness of exact TDK and TDKR parameterized by solution size
    Invoked to separate the PAS time bound from FPT exact solvability.

pith-pipeline@v0.9.0 · 5999 in / 1334 out tokens · 47505 ms · 2026-05-25T15:23:10.111999+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems

    cs.DS 2026-04 unverdicted novelty 7.0

    Near-tight (2/3-ε) approximation for identical-capacity bottleneck multiple knapsack and (1/2-ε) for arbitrary capacities, with matching inapproximability.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · cited by 1 Pith paper

  1. [1]

    Approximation schemes for maximum weight independent set of rectangles

    Anna Adamaszek and Andreas Wiese. Approximation schemes for maximum weight independent set of rectangles. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013) , pages 400--409. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.50, http://dx.doi.org/10.1109/FOCS.2013.50 doi:10.1109/FOCS.2013.50

    work page doi:10.1109/focs.2013.50 2013

  2. [2]

    A quasi- PTAS for the two-dimensional geometric knapsack problem

    Anna Adamaszek and Andreas Wiese. A quasi- PTAS for the two-dimensional geometric knapsack problem. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015) , pages 1491--1505. SIAM, 2015. URL: http://dl.acm.org/citation.cfm?id=2722129.2722227

    work page arXiv 2015

  3. [3]

    Sch\'emas d'approximation et Complexit\'e Param\'etr\'ee , R apport du stage ( DEA )

    Cristina Bazgan. Sch\'emas d'approximation et Complexit\'e Param\'etr\'ee , R apport du stage ( DEA ). Technical report, Universit\'ee Paris Sud, 1995

    work page 1995

  4. [4]

    Parameterized approximability of maximizing the spread of influence in networks

    Cristina Bazgan, Morgan Chopin, Andr \' e Nichterlein, and Florian Sikora. Parameterized approximability of maximizing the spread of influence in networks. J. Discrete Algorithms , 27:54--65, 2014. URL: http://dx.doi.org/10.1016/j.jda.2014.05.001, http://dx.doi.org/10.1016/j.jda.2014.05.001 doi:10.1016/j.jda.2014.05.001

    work page doi:10.1016/j.jda.2014.05.001 2014

  5. [5]

    Parameterized inapproximability of target set selection and generalizations

    Cristina Bazgan, Morgan Chopin, Andr \' e Nichterlein, and Florian Sikora. Parameterized inapproximability of target set selection and generalizations. Computability , 3(2):135--145, 2014. URL: http://dx.doi.org/10.3233/COM-140030, http://dx.doi.org/10.3233/COM-140030 doi:10.3233/COM-140030

    work page doi:10.3233/com-140030 2014

  6. [6]

    Parameterized inapproximability of degree anonymization

    Cristina Bazgan and Andr \' e Nichterlein. Parameterized inapproximability of degree anonymization. In Proceedings of the 9th International Symposium on Parameterized and Exact Computation (IPEC 2014) , pages 75--84, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13524-3_7, http://dx.doi.org/10.1007/978-3-319-13524-3_7 doi:10.1007/978-3-319-13524-3_7

    work page doi:10.1007/978-3-319-13524-3_7 2014

  7. [7]

    Bodlaender, P l Gr n s Drange, Markus S

    Hans L. Bodlaender, P l Gr n s Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-approximation algorithm for treewidth. SIAM J. Comput. , 45(2):317--378, 2016. URL: http://dx.doi.org/10.1137/130947374, http://dx.doi.org/10.1137/130947374 doi:10.1137/130947374

    work page doi:10.1137/130947374 2016

  8. [8]

    Consensus patterns (probably) has no EPTAS

    Christina Boucher, Christine Lo, and Daniel Lokshantov. Consensus patterns (probably) has no EPTAS . In Proceedings of the 23rd Annual European Symposium ( ESA 2015) , pages 239--250, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_21, http://dx.doi.org/10.1007/978-3-662-48350-3_21 doi:10.1007/978-3-662-48350-3_21

    work page doi:10.1007/978-3-662-48350-3_21 2015

  9. [9]

    Fixed-parameter approximation: Conceptual framework and approximability results

    Liming Cai and Xiuzhen Huang. Fixed-parameter approximation: Conceptual framework and approximability results. In Parameterized and Exact Computation ( IWPEC 2006) , pages 96--108, 2006. URL: http://dx.doi.org/10.1007/11847250_9, http://dx.doi.org/10.1007/11847250_9 doi:10.1007/11847250_9

    work page doi:10.1007/11847250_9 2006

  10. [10]

    On the efficiency of polynomial time approximation schemes

    Marco Cesati and Luca Trevisan. On the efficiency of polynomial time approximation schemes. Inf. Process. Lett. , 64(4):165--171, 1997. URL: http://dx.doi.org/10.1016/S0020-0190(97)00164-6, http://dx.doi.org/10.1016/S0020-0190(97)00164-6 doi:10.1016/S0020-0190(97)00164-6

    work page doi:10.1016/s0020-0190(97)00164-6 1997

  11. [11]

    Chalermsook and J

    P. Chalermsook and J. Chuzhoy. Maximum independent set of rectangles. In Proceedings of the 20 th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09) , pages 892--901. SIAM, 2009

    work page 2009

  12. [12]

    Approximation algorithms for maximum independent set of pseudo-disks

    Timothy M Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry , 48(2):373--392, 2012

    work page 2012

  13. [13]

    On parameterized approximability

    Yijia Chen, Martin Grohe, and Magdalena Gr \" u ber. On parameterized approximability. In Parameterized and Exact Computation (IWPEC 2006) , pages 109--120, 2006. URL: http://dx.doi.org/10.1007/11847250_10, http://dx.doi.org/10.1007/11847250_10 doi:10.1007/11847250_10

    work page doi:10.1007/11847250_10 2006

  14. [14]

    The constant inapproximability of the parameterized dominating set problem

    Yijia Chen and Bingkai Lin. The constant inapproximability of the parameterized dominating set problem. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016) , pages 505--514, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.61, http://dx.doi.org/10.1109/FOCS.2016.61 doi:10.1109/FOCS.2016.61

    work page doi:10.1109/focs.2016.61 2016

  15. [15]

    On approximating maximum independent set of rectangles

    Julia Chuzhoy and Alina Ene. On approximating maximum independent set of rectangles. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016) , pages 820--829, 2016. URL: https://doi.org/10.1109/FOCS.2016.92, http://dx.doi.org/10.1109/FOCS.2016.92 doi:10.1109/FOCS.2016.92

    work page doi:10.1109/focs.2016.92 2016

  16. [16]

    A fixed parameter tractable approximation scheme for the optimal cut graph of a surface

    Vincent Cohen - Addad and Arnaud de Mesmay. A fixed parameter tractable approximation scheme for the optimal cut graph of a surface. In Proceedings of the 23rd Annual European Symposium ( ESA 2015) , pages 386--398, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_33, http://dx.doi.org/10.1007/978-3-662-48350-3_33 doi:10.1007/978-3-662-48350-3_33

    work page doi:10.1007/978-3-662-48350-3_33 2015

  17. [17]

    Lower bounds for approximation schemes for closest string

    Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Lower bounds for approximation schemes for closest string. In 15th Scandinavian Symposium and Workshops on Algorithm Theory ( SWAT 2016) , pages 12:1--12:10, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.12, http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.12 doi:10.4...

    work page doi:10.4230/lipics.swat.2016.12 2016

  18. [18]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: on completeness for W[1] . Theor. Comput. Sci. , 141(1 & 2):109--131, 1995. URL: http://dx.doi.org/10.1016/0304-3975(94)00097-3, http://dx.doi.org/10.1016/0304-3975(94)00097-3 doi:10.1016/0304-3975(94)00097-3

    work page doi:10.1016/0304-3975(94)00097-3 1995

  19. [19]

    Downey, Michael R

    Rodney G. Downey, Michael R. Fellows, and Catherine McCartin. Parameterized approximation problems. In Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC 2006) , pages 121--129, 2006. URL: http://dx.doi.org/10.1007/11847250_11, http://dx.doi.org/10.1007/11847250_11 doi:10.1007/11847250_11

    work page doi:10.1007/11847250_11 2006

  20. [20]

    Polynomial-time approximation schemes for geometric intersection graphs

    Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing , 34(6):1302--1323, 2005

    work page 2005

  21. [21]

    Fast algorithms for shortest paths in planar graphs, with applications

    Greg N Federickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing , 16(6):1004--1022, 1987

    work page 1987

  22. [22]

    Fixed parameter approximations for k-center problems in low highway dimension graphs

    Andreas Emil Feldmann. Fixed parameter approximations for k-center problems in low highway dimension graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming ( ICALP 2015) , pages 588--600, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_47, http://dx.doi.org/10.1007/978-3-662-47666-6_47 doi:10.1007/978-3-...

    work page doi:10.1007/978-3-662-47666-6_47 2015

  23. [23]

    Fellows, Ariel Kulik, Frances A

    Michael R. Fellows, Ariel Kulik, Frances A. Rosamond, and Hadas Shachnai. Parameterized approximation via fidelity preserving transformations. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming ( ICALP 2012) , pages 351--362, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_30, http://dx.doi.org/10.1007/978-3...

    work page doi:10.1007/978-3-642-31594-7_30 2012

  24. [24]

    Optimal packing and covering in the plane are NP -complete

    Robert J Fowler, Michael S Paterson, and Steven L Tanimoto. Optimal packing and covering in the plane are NP -complete. Information processing letters , 12(3):133--137, 1981

    work page 1981

  25. [25]

    Approximating geometric knapsack via L -packings

    Waldo G \' a lvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, and Andreas Wiese. Approximating geometric knapsack via L -packings. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017) , pages 260--271, 2017. URL: https://doi.org/10.1109/FOCS.2017.32, http://dx.doi.org/10.1109/FOCS.2017.32 ...

    work page doi:10.1109/focs.2017.32 2017

  26. [26]

    Faster approximation schemes for the two-dimensional knapsack problem

    Sandy Heydrich and Andreas Wiese. Faster approximation schemes for the two-dimensional knapsack problem. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 79--98. SIAM, 2017

    work page 2017

  27. [27]

    A polynomial time approximation scheme for the square packing problem

    Klaus Jansen and Roberto Solis-Oba. A polynomial time approximation scheme for the square packing problem. In International Conference on Integer Programming and Combinatorial Optimization , pages 184--198. Springer, 2008

    work page 2008

  28. [28]

    On rectangle packing: maximizing benefits

    Klaus Jansen and Guochaun Zhang. On rectangle packing: maximizing benefits. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms , pages 204--213. SIAM, 2004

    work page 2004

  29. [29]

    Sudeshna Kolay, Pranabendu Misra, M. S. Ramanujan, and Saket Saurabh. Parameterized approximations via d-skew-symmetric multicut. In Proceedings of the 39th International Symposium (MFCS 2014) , pages 457--468, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_39, http://dx.doi.org/10.1007/978-3-662-44465-8_39 doi:10.1007/978-3-662-44465-8_39

    work page doi:10.1007/978-3-662-44465-8_39 2014

  30. [30]

    Parameterized approximation schemes using graph widths

    Michael Lampis. Parameterized approximation schemes using graph widths. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming ( ICALP 2014) , pages 775--786, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_64, http://dx.doi.org/10.1007/978-3-662-43948-7_64 doi:10.1007/978-3-662-43948-7_64

    work page doi:10.1007/978-3-662-43948-7_64 2014

  31. [31]

    Packing squares into a square

    Joseph YT Leung, Tommy W Tam, Chin S Wong, Gilbert H Young, and Francis YL Chin. Packing squares into a square. Journal of Parallel and Distributed Computing , 10(3):271--275, 1990

    work page 1990

  32. [32]

    Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017) , pages 224--237, 2017. URL: https://doi.org/10.1145/3055399.3055456, http://dx.doi.org/10.1145/3055399.3055456 doi:10.1145/3055399.3055456

    work page doi:10.1145/3055399.3055456 2017

  33. [33]

    Efficient approximation schemes for geometric problems? In Algorithms - Proceedings of ESA 2005 , pages 448--459, 2005

    D \' a niel Marx. Efficient approximation schemes for geometric problems? In Algorithms - Proceedings of ESA 2005 , pages 448--459, 2005. URL: http://dx.doi.org/10.1007/11561071_41, http://dx.doi.org/10.1007/11561071_41 doi:10.1007/11561071_41

    work page doi:10.1007/11561071_41 2005

  34. [34]

    Parameterized complexity and approximation algorithms

    D \' a niel Marx. Parameterized complexity and approximation algorithms. Comput. J. , 51(1):60--78, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm048, http://dx.doi.org/10.1093/comjnl/bxm048 doi:10.1093/comjnl/bxm048

    work page doi:10.1093/comjnl/bxm048 2008