Simplified tight analysis of Johnson's algorithm

DOI10.1016/J.IPL.2004.08.001MaRDI QIDQ834942zbMATH OpenOpenAlexFDO

Authors Lars Engebretsen

Publication date 27 August 2009

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

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

zbMATH Keywords

algorithmsanalysis of algorithmsapproximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

Recommendations

• Tight bound on Johnson's algorithm for maximum satisfiability
• Probabilistic bounds and algorithms for the maximum satisfiability problem
• Randomized variants of Johnson's algorithm for MAX SAT
• On the Approximation of Maximum Satisfiability
• New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem

Cites work

• Approximation algorithms for combinatorial problems
• On the Approximation of Maximum Satisfiability
• Tight bound on Johnson's algorithm for maximum satisfiability

Cited in

(2)

• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• On extensions of the deterministic online model for bipartite matching and max-sat

This page was built for publication: Simplified tight analysis of Johnson's algorithm

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