Tight bound on Johnson's Algorithm for Max-SAT Conference Paper

abstract

• 1997 IEEE. We present a new technique that gives a more thorough analysis on Johnson's classical algorithm for the maximum satisfiability problem. In contrast to the common belief for two decades that Johnson's algorithm has performance ratio 1/2, we show that the performance ratio is 2/3, and that this bound is tight. Moreover we show that simple generalizations of Johnson's algorithm do not improve the performance ratio bound 2/3.

name of conference

• Proceedings of Computational Complexity. Twelfth Annual IEEE Conference

authors

• Chen, Jianer

published proceedings

• TWELFTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS

author list (cited authors)

• Chen, J. E., Friesen, D. K., & Zheng, H.

citation count

• 6

complete list of authors

• Chen, JE||Friesen, DK||Zheng, H

publication date

• January 1997

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• Proceedings of the Annual IEEE Conference on Computational Complexity  Journal

Digital Object Identifier (DOI)

• 10.1109/ccc.1997.612322

International Standard Book Number (ISBN) 10

• 0-7803-4267-4

start page

• 274

end page

• 281

URL

• http://dx.doi.org/10.1109/ccc.1997.612322