Adding cardinality constraints to integer programs with applications to maximum satisfiability

DOI10.1016/J.IPL.2007.08.024MaRDI QIDQ2380072zbMATH OpenOpenAlexFDO

Authors Markus Bläser, Thomas Heynen, Bodo Manthey

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.08.024

zbMATH Keywords

randomized algorithmssatisfiability

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Integer programming (90C10) Discrete location and assignment (90B80)

Recommendations

• scientific article; zbMATH DE number 1979498
• An approximation algorithm for MAX-2-SAT with cardinality constraint
• Best possible approximation algorithm for MAX SAT with cardinality constraint.
• scientific article; zbMATH DE number 1182773
• scientific article; zbMATH DE number 1303558

Cites work

• scientific article; zbMATH DE number 1979498 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• An approximation algorithm for MAX-2-SAT with cardinality constraint
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Best possible approximation algorithm for MAX SAT with cardinality constraint.
• Efficient approximation of product distributions
• Improved approximation algorithms for MAX SAT
• NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Some optimal inapproximability results

Cited in

(5)

• Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint
• Best possible approximation algorithm for MAX SAT with cardinality constraint.
• An approximation algorithm for MAX-2-SAT with cardinality constraint
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• On a Reformulation of Mathematical Programs with Cardinality Constraints

This page was built for publication: Adding cardinality constraints to integer programs with applications to maximum satisfiability

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