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

DOI10.1007/B13632zbMATH Open1266.68229OpenAlexW1827234103MaRDI QIDQ5897255FDOQ5897255

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

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

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• Simple Approximation Algorithms for Balanced MAX 2SAT
• On MAX-SAT with cardinality constraint
• Improved FPT approximation scheme and approximate kernel for biclique-free max \(k\)-weight SAT: greedy strikes back
• A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach

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)