Best possible approximation algorithm for MAX SAT with cardinality constraint.

DOI10.1007/S00453-001-0019-5MaRDI QIDQ5945919zbMATH OpenOpenAlexFDO

Authors Maxim 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

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

Recommendations

• Best possible approximation algorithm for MAX SAT with cardinality constraint
• scientific article; zbMATH DE number 1303558
• An approximation algorithm for MAX-2-SAT with cardinality constraint
• Improved approximation algorithms for max-2SAT with cardinality constraint
• Adding cardinality constraints to integer programs with applications to maximum satisfiability

Cited in

(11)

• Adding cardinality constraints to integer programs with applications to maximum satisfiability
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• Best possible approximation algorithm for MAX SAT with cardinality constraint
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• An approximation algorithm for MAX-2-SAT with cardinality constraint
• Max-SAT with cardinality constraint parameterized by the number of clauses
• On MAX-SAT with cardinality constraint
• On MAX-SAT with cardinality constraint
• Improved FPT approximation scheme and approximate kernel for biclique-free max k-weight SAT: greedy strikes back
• Satisfiability to coverage in presence of fairness, matroid, and global constraints
• Max-SAT with cardinality constraint parameterized by the number of clauses

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5945919)