2026-07-25T03:06:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21004 2024-09-16T06:02:38Z ddc:004 open_access

On the NP-Hardness Approximation Curve for Max-2Lin(2) Martinsson, Björn Inapproximability NP-hardness 2Lin(2) Max-Cut Gadget In the Max-2Lin(2) problem you are given a system of equations on the form x_i + x_j ≡ b mod 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^k - 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Björn Martinsson 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.11 urn:nbn:de:0030-drops-210049 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.11 eng https://creativecommons.org/licenses/by/4.0/legalcode