Moving intervals for packing and covering
Rain Jiang, Jiang, Kai, Minghui Jiang · arXiv (Cornell University) · 2021
We study several problems on geometric packing and covering with movement. Given a family $\mathcal{I}$ of $n$ intervals of $κ$ distinct lengths, and another interval $B$, can we pack the intervals in $\mathcal{I}$ inside $B$ (respectively, cover $B$ by the intervals in $\mathcal{I}$) by moving $τ$ intervals and keeping the other $σ= n - τ$ intervals unmoved? We show that both packing and covering are W[1]-hard with any one of $κ$, $τ$, and $σ$ as single parameter, but are FPT with combined parameters $κ$ and $τ$. We also obtain improved polynomial-time algorithms for packing and covering, including an $O(n\log^2 n)$ time algorithm for covering, when all intervals in $\mathcal{I}$ have the same length.