2026-07-23T06:19:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11239 2024-03-06T10:47:46Z ddc:004 open_access

Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder Austrin, Per Stanković, Aleksa Constraint satisfaction problems global cardinality constraints semidefinite programming inapproximability Unique Games Conjecture Max-Cut Max-2-Sat Assuming the Unique Games Conjecture, we show that existing approximation algorithms for some Boolean Max-2-CSPs with cardinality constraints are optimal. In particular, we prove that Max-Cut with cardinality constraints is UG-hard to approximate within ~~0.858, and that Max-2-Sat with cardinality constraints is UG-hard to approximate within ~~0.929. In both cases, the previous best hardness results were the same as the hardness of the corresponding unconstrained Max-2-CSP (~~0.878 for Max-Cut, and ~~0.940 for Max-2-Sat). The hardness for Max-2-Sat applies to monotone Max-2-Sat instances, meaning that we also obtain tight inapproximability for the Max-k-Vertex-Cover problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Per Austrin and Aleksa Stanković 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.24 urn:nbn:de:0030-drops-112394 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.24 eng https://creativecommons.org/licenses/by/3.0/legalcode