On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913427838992384 |
|---|---|
| author | S., Karthik C. Lee, Euiwoong Manurangsi, Pasin |
| author_facet | S., Karthik C. Lee, Euiwoong Manurangsi, Pasin |
| contents | Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on $k$ variables and alphabet size $n$, it is W[1]-hard parameterized by $k$ to distinguish if the input is perfectly satisfiable or if every assignment to the input violates 1% of the constraints.
An important implication of PIH is that it yields the tight parameterized inapproximability of the $k$-maxcoverage problem. In the $k$-maxcoverage problem, we are given as input a set system, a threshold $τ>0$, and a parameter $k$ and the goal is to determine if there exist $k$ sets in the input whose union is at least $τ$ fraction of the entire universe. PIH is known to imply that it is W[1]-hard parameterized by $k$ to distinguish if there are $k$ input sets whose union is at least $τ$ fraction of the universe or if the union of every $k$ input sets is not much larger than $τ\cdot (1-\frac{1}{e})$ fraction of the universe.
In this work we present a gap preserving FPT reduction (in the reverse direction) from the $k$-maxcoverage problem to the aforementioned 2-CSP problem, thus showing that the assertion that approximating the $k$-maxcoverage problem to some constant factor is W[1]-hard implies PIH. In addition, we present a gap preserving FPT reduction from the $k$-median problem (in general metrics) to the $k$-maxcoverage problem, further highlighting the power of gap preserving FPT reductions over classical gap preserving polynomial time reductions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_08917 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP S., Karthik C. Lee, Euiwoong Manurangsi, Pasin Computational Complexity Data Structures and Algorithms Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on $k$ variables and alphabet size $n$, it is W[1]-hard parameterized by $k$ to distinguish if the input is perfectly satisfiable or if every assignment to the input violates 1% of the constraints. An important implication of PIH is that it yields the tight parameterized inapproximability of the $k$-maxcoverage problem. In the $k$-maxcoverage problem, we are given as input a set system, a threshold $τ>0$, and a parameter $k$ and the goal is to determine if there exist $k$ sets in the input whose union is at least $τ$ fraction of the entire universe. PIH is known to imply that it is W[1]-hard parameterized by $k$ to distinguish if there are $k$ input sets whose union is at least $τ$ fraction of the universe or if the union of every $k$ input sets is not much larger than $τ\cdot (1-\frac{1}{e})$ fraction of the universe. In this work we present a gap preserving FPT reduction (in the reverse direction) from the $k$-maxcoverage problem to the aforementioned 2-CSP problem, thus showing that the assertion that approximating the $k$-maxcoverage problem to some constant factor is W[1]-hard implies PIH. In addition, we present a gap preserving FPT reduction from the $k$-median problem (in general metrics) to the $k$-maxcoverage problem, further highlighting the power of gap preserving FPT reductions over classical gap preserving polynomial time reductions. |
| title | On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.08917 |