Improved approximation algorithms for max-2SAT with cardinality constraint

DOI10.1007/3-540-36136-7_17MaRDI QIDQ4425953zbMATH OpenFDO

Authors Markus Bläser, Bodo Manthey

Publication date 14 September 2003

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2518/25180187.htm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• An approximation algorithm for MAX-2-SAT with cardinality constraint
• Improved approximation algorithms for MAX SAT
• scientific article; zbMATH DE number 1445292
• Improving exact algorithms for MAX-2-SAT
• Approximation and Online Algorithms
• Best possible approximation algorithm for MAX SAT with cardinality constraint
• scientific article; zbMATH DE number 1552232
• scientific article; zbMATH DE number 1258327
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
• Improved exact algorithms for MAX-SAT

Cited in

(11)

• Approximating a generalization of MAX 2SAT and MIN 2SAT
• Adding cardinality constraints to integer programs with applications to maximum satisfiability
• Simple Approximation Algorithms for Balanced MAX 2SAT
• 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
• Best possible approximation algorithm for MAX SAT with cardinality constraint.
• Parameterized approximation scheme for biclique-free max k-weight SAT and max coverage
• 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

This page was built for publication: Improved approximation algorithms for max-2SAT with cardinality constraint

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