An approximation algorithm for MAX-2-SAT with cardinality constraint

DOI10.1007/B13632MaRDI QIDQ5897255zbMATH OpenOpenAlexFDO

Authors Thomas Hofmeister

Publication date 3 March 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b13632

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1979498
• scientific article; zbMATH DE number 1182773
• Approximation and Online Algorithms
• Best possible approximation algorithm for MAX SAT with cardinality constraint.
• Adding cardinality constraints to integer programs with applications to maximum satisfiability

Cited in

(11)

• Approximating a generalization of MAX 2SAT and MIN 2SAT
• Adding cardinality constraints to integer programs with applications to maximum satisfiability
• On MAX-SAT with cardinality constraint
• Best possible approximation algorithm for MAX SAT with cardinality constraint.
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• scientific article; zbMATH DE number 1979498 (Why is no real title available?)
• Simple Approximation Algorithms for Balanced MAX 2SAT
• On MAX-SAT with cardinality constraint
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach
• Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back

Describes a project that uses

Uses Software

• MAX-2-SAT

This page was built for publication: An approximation algorithm for MAX-2-SAT with cardinality constraint

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