Best possible approximation algorithm for MAX SAT with cardinality constraint.

DOI10.1007/s00453-001-0019-5zbMath1136.90493OpenAlexW2181129831MaRDI QIDQ5945919

M. I. Sviridenko

Publication date: 9 January 2002

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-001-0019-5

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

Adding cardinality constraints to integer programs with applications to maximum satisfiability ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder

This page was built for publication: Best possible approximation algorithm for MAX SAT with cardinality constraint.