Answers are grounded in this paper and cite their sources.
In the Max-2Lin(2) problem you are given a system of equations on the form xᵢ + xⱼ ≡ b 2, and your objective is to find an assignment that satisfies as many equations as possible. Let c ∈ [0.5, 1] denote the maximum fraction of satisfiable equations. In this paper we construct a curve $s (c)$ such that it is NP-hard to find a solution satisfying at least a fraction s of equations. This curve either matches or improves all of the previously known inapproximability NP-hardness results for Max-2Lin(2). In particular, we show that if c 0.9232 then 1 - s (c)/1 - c > 1.48969, which improves the NP-hardness inapproximability constant for the min deletion version of Max-2Lin(2). Our work complements the work of O'Donnell and Wu that studied the same question assuming the Unique Games Conjecture. Similar to earlier inapproximability results for Max-2Lin(2), we use a gadget reduction from the (2ᵏ - 1)-ary Hadamard predicate. Previous works used k ranging from $2$ to $4$. Our main result is a procedure for taking a gadget for some fixed k, and use it as a building block to construct better and better gadgets as k tends to infinity. Our method can be used to boost the result of both smaller gadgets created by hand $(k = 3)$ or larger gadgets constructed using a computer $(k = 4)$.
No takes yet. Share an insight, caveat, or question.
Björn Martinsson (2024) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: