Simplified tight analysis of Johnson's algorithm

DOI10.1016/J.IPL.2004.08.001zbMath1173.68818OpenAlexW2024650545MaRDI QIDQ834942

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)

Related Items (2)

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

Cites Work

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

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