Covering points by boundaries of axis-parallel rectangles is NP-complete in the free-placement setting, W[1]-hard when rectangles are preset, and fixed-parameter tractable in the solution size k.
Random separation: A new method for solving fixed-cardinality optimization problems
3 Pith papers cite this work, alongside 191 external citations. Polarity classification is still indexing.
3
Pith papers citing it
191
external citations · OpenAlex
years
2026 3representative citing papers
Under Gap-ETH, the n^{O(1/ε^{d-1})}-time shifting PTAS is optimal for maximum independent set, minimum dominating set, maximum induced forest, maximum induced matching, and minimum piercing set on unit ball graphs in every constant dimension d≥2.
Ulam k-center is FPT for k+d but admits no polynomial kernel unless NP is in coNP/poly; k-median is W[1]-hard for d yet FPT for k+d via a polynomial kernel.
citing papers explorer
-
Covering Points with Rectangular Boundaries
Covering points by boundaries of axis-parallel rectangles is NP-complete in the free-placement setting, W[1]-hard when rectangles are preset, and fixed-parameter tractable in the solution size k.
-
Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes
Under Gap-ETH, the n^{O(1/ε^{d-1})}-time shifting PTAS is optimal for maximum independent set, minimum dominating set, maximum induced forest, maximum induced matching, and minimum piercing set on unit ball graphs in every constant dimension d≥2.
-
Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
Ulam k-center is FPT for k+d but admits no polynomial kernel unless NP is in coNP/poly; k-median is W[1]-hard for d yet FPT for k+d via a polynomial kernel.