Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities

The \textsc{Capacitated $d$-Hitting Set} problem involves a universe $U$ with a capacity function $\mathsf{c}\mathsf{a}\mathsf{p}:U\to \mathbb{N}$ and a collection $\mathcal{A}$ of subsets of $U$, each of size at most $d$. The goal is to find a minimum subset $S\subseteq U$ and an assignment $\phi :\mathcal{A}\to S$ such that for every $A\in \mathcal{A}$, $\phi (A)\in A$, and for each $x\in U$, $\mathrm{\mid }{\phi }^{-1}(x)\mathrm{\mid }\le \mathsf{c}\mathsf{a}\mathsf{p}(x)$. For $d=2$, this is known as $\text{textsc}CapacitatedVertexCover$. In the weighted variant, each element of $U$ has a positive integer weight, with the objective of finding a minimum-weight capacitated hitting set. Chuzhoy and Naor [SICOMP 2006] provided a factor-3 approximation for $\text{textsc}CapacitatedVertexCover$ and showed that the weighted case lacks an $o(\log n)$-approximation unless $P=NP$. Kao and Wong [SODA 2017] later independently achieved a $d$-approximation for \textsc{Capacitated $d$-Hitting Set}, with no $d-\epsilon$ improvements possible under the Unique Games Conjecture. Our main result is a parameterized approximation algorithm with runtime ${\left(\frac{k}{\epsilon }\right)}^k{2}^{k^{O(kd)}}(\mathrm{\mid }U\mathrm{\mid }+\mathrm{\mid }\mathcal{A}\mathrm{\mid }{)}^{O(1)}$ that either concludes no solution of size $\le k$ exists or finds $S$ of size $\le 4\mathrm{/}3\cdot k$ and weight at most $2+\epsilon$ times the minimum weight for solutions of size $\le k$. We further show that no FPT-approximation with factor $c>1$ exists for unweighted \textsc{Capacitated $d$-Hitting Set} with $d\ge 3$, nor with factor $2-\epsilon$ for the weighted version, assuming the Exponential Time Hypothesis. These results extend to $\text{textsc}CapacitatedVertexCover$ in multigraphs. Additionally, a variant of multi-dimensional $\text{textsc}Knapsack$ is shown hard to FPT-approximate within $2-\epsilon$.