Change search
ReferencesLink to record
Permanent link

Direct link
Simplified tight analysis of Johnson's algorithm
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2004 (English)In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 92, no 4, 207-210 p.Article in journal (Refereed) Published
Abstract [en]

In their paper "Tight bound on Johnson's algorithm for maximum satisfiability" [J. Comput. System Sci. 58 (3) (1999) 622-640] Chen, Friesen and Zheng provided a tight bound on the approximation ratio of Johnson's algorithm for Maximum Satisfiability [J. Comput. System Sci. 9 (3) (1974) 256-278]. We give a simplified proof of their result and investigate to what extent it may be generalized to non-Boolean domains.

Place, publisher, year, edition, pages
2004. Vol. 92, no 4, 207-210 p.
Keyword [en]
algorithms, analysis of algorithms, approximation algorithms
National Category
Computer Science
URN: urn:nbn:se:kth:diva-39786DOI: 10.1016/j.ipl.2004.08.001ISI: 000224824300008ScopusID: 2-s2.0-5744247720OAI: diva2:442180
QC 20110920Available from: 2011-09-20 Created: 2011-09-12 Last updated: 2011-09-20Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Engebretsen, Lars
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Information Processing Letters
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 24 hits
ReferencesLink to record
Permanent link

Direct link