On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP

Karthik C. S., Euiwoong Lee, Pasin Manurangsi

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 alphab…