Approximation Algorithms for Label Cover and The Log-Density Threshold
Eden Chlamtáč, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan · 2017
Many known optimal NP-hardness of approximation results are reductions from a problem called Label Cover. The input is a bipartite graph G = (L, R, E) and each edge e = (x,y) ∊ E carries a projection π∊ that maps labels to x to labels to y. The objective is to find a labeling of the vertices that satisfies as many of the projections as possible. It is believed that the best approximation ratio efficiently achievable for Label-Cover is of the form N−c where N = nk, n is the number of vertices, k is the number of labels, and 0 ≤ c 0, a polynomial-time approximation algorithm for semirandom Label-Cover whose approximation ratio is In our semi-random model, the input graph is random (or even just expanding), and the projections on the edges are arbitrary. For worst-case Label-Cover we show a polynomial- time algorithm whose approximation ratio is roughly Ν-°·233. The previous best efficient approximation ratio was Ν−0·25. We present some evidence towards an Ν−c threshold by constructing integrality gaps for Νω(1) rounds of the Sum-of-squares/Lasserre hierarchy of the natural relaxation of Label Cover. For general 2CSP the “log density threshold” is Ν−0·25, and we give a polynomial-time algorithm in the semi-random model whose approximation ratio is Ν−0·25+∊ for any ∊ > 0.