Improved Approximation Algorithms for MAX SAT

DOI10.1006/jagm.2001.1202zbMath0990.68078OpenAlexW2018025029MaRDI QIDQ2777611

David P. Williamson, Takao Asano

Publication date: 14 August 2002

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.2001.1202

zbMATH Keywords

maximum satisfiability problem

Mathematics Subject Classification ID

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

Related Items (8)

An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT ⋮ Local Search to Approximate Max NAE-$$k$$-Sat Tightly ⋮ Adding cardinality constraints to integer programs with applications to maximum satisfiability ⋮ Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles ⋮ Approximating Max NAE-\(k\)-SAT by anonymous local search ⋮ Dealing with 4-variables by resolution: an improved MaxSAT algorithm ⋮ The labeled perfect matching in bipartite graphs ⋮ Unnamed Item

This page was built for publication: Improved Approximation Algorithms for MAX SAT