Vi presenterar nya tekniker som ger en mer grundlig analys av Johnsons klassiska algoritm för problemet med maximal tillfredsställelse. I motsats till den vanliga uppfattningen under två decennier att Johnsons Algoritm har prestandaförhållande 1Â2, visar vi att prestandaförhållandet är 2Â3 och att denna gräns är tight. Dessutom visar vi att enkla generaliseringar av Johnsons algoritm inte förbättrar prestandaförhållandet bundet 2Â3. Akademisk press
Chen et al REF visade att Johnsons algoritm uppnår detta 2/3 approximationsförhållande.
Tight Bound on Johnson's Algorithm for Maximum Satisfiability
{'venue': 'J. Comput. Syst. Sci.', 'journal': 'J. Comput. Syst. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}