Inapproximability results for set splitting and satisfiability problems with no mixed clauses
From MaRDI portal
Publication:1879246
DOI10.1007/s00453-003-1072-zzbMath1095.68036OpenAlexW2806518615MaRDI QIDQ1879246
Publication date: 22 September 2004
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-003-1072-z
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (7)
From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ Almost envy-freeness for groups: improved bounds via discrepancy theory ⋮ Committee polyhedral separability: complexity and polynomial approximation ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Hypergraph cuts above the average ⋮ Clustering with qualitative information ⋮ Algorithmic Aspects of Combinatorial Discrepancy
This page was built for publication: Inapproximability results for set splitting and satisfiability problems with no mixed clauses
