Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910673018028032 |
|---|---|
| author | Lokshtanov, Daniel Sahu, Abhishek Saurabh, Saket Surianarayanan, Vaishali Xue, Jie |
| author_facet | Lokshtanov, Daniel Sahu, Abhishek Saurabh, Saket Surianarayanan, Vaishali Xue, Jie |
| contents | The \textsc{Capacitated $d$-Hitting Set} problem involves a universe $U$ with a capacity function $\mathsf{cap}: U \rightarrow \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 $ϕ: \mathcal{A} \rightarrow S$ such that for every $A \in \mathcal{A}$, $ϕ(A) \in A$, and for each $x \in U$, $|ϕ^{-1}(x)| \leq \mathsf{cap}(x)$. For $d=2$, this is known as \textsc{Capacitated Vertex Cover}. 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 \textsc{Capacitated Vertex Cover} 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 - ε$ improvements possible under the Unique Games Conjecture. Our main result is a parameterized approximation algorithm with runtime $\left(\frac{k}ε\right)^k 2^{k^{O(kd)}}(|U|+|\mathcal{A}|)^{O(1)}$ that either concludes no solution of size $\leq k$ exists or finds $S$ of size $\leq 4/3 \cdot k$ and weight at most $2+ε$ times the minimum weight for solutions of size $\leq k$. We further show that no FPT-approximation with factor $c > 1$ exists for unweighted \textsc{Capacitated $d$-Hitting Set} with $d \geq 3$, nor with factor $2 - ε$ for the weighted version, assuming the Exponential Time Hypothesis. These results extend to \textsc{Capacitated Vertex Cover} in multigraphs. Additionally, a variant of multi-dimensional \textsc{Knapsack} is shown hard to FPT-approximate within $2 - ε$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_20900 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities Lokshtanov, Daniel Sahu, Abhishek Saurabh, Saket Surianarayanan, Vaishali Xue, Jie Data Structures and Algorithms The \textsc{Capacitated $d$-Hitting Set} problem involves a universe $U$ with a capacity function $\mathsf{cap}: U \rightarrow \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 $ϕ: \mathcal{A} \rightarrow S$ such that for every $A \in \mathcal{A}$, $ϕ(A) \in A$, and for each $x \in U$, $|ϕ^{-1}(x)| \leq \mathsf{cap}(x)$. For $d=2$, this is known as \textsc{Capacitated Vertex Cover}. 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 \textsc{Capacitated Vertex Cover} 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 - ε$ improvements possible under the Unique Games Conjecture. Our main result is a parameterized approximation algorithm with runtime $\left(\frac{k}ε\right)^k 2^{k^{O(kd)}}(|U|+|\mathcal{A}|)^{O(1)}$ that either concludes no solution of size $\leq k$ exists or finds $S$ of size $\leq 4/3 \cdot k$ and weight at most $2+ε$ times the minimum weight for solutions of size $\leq k$. We further show that no FPT-approximation with factor $c > 1$ exists for unweighted \textsc{Capacitated $d$-Hitting Set} with $d \geq 3$, nor with factor $2 - ε$ for the weighted version, assuming the Exponential Time Hypothesis. These results extend to \textsc{Capacitated Vertex Cover} in multigraphs. Additionally, a variant of multi-dimensional \textsc{Knapsack} is shown hard to FPT-approximate within $2 - ε$. |
| title | Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.20900 |