Paper Info
Title
An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem.
Abstract
We evaluate the performance of fast approximation algorithms for MAXï¾źSAT on the comprehensive benchmark sets from the SAT and MAXï¾źSAT contests. Our examination of a broad range of algorithmic techniques reveals that greedy algorithms offer particularly striking performance, delivering very good solutions at low computational cost. Interestingly, their relative ranking does not follow their worst case behavior. Johnson's deterministic algorithm is constantly better than the randomized greedy algorithm of Poloczek et al.ï¾ź[31], but in turn is outperformed by the derandomization of the latter: this 2-pass algorithm satisfies more thanï¾ź$$99\\,\\%$$99% of the clauses for instances stemming from industrial applications. In general it performs considerably better than non-oblivious local search, Tabu Search, WalkSat, and several state-of-the-art complete and incomplete solvers, while being much faster. But the 2-pass algorithm does not achieve the excellent performance of Spears' computationally intense simulated annealing. Therefore, we propose a new hybrid algorithm that combines the strengths of greedy algorithms and stochastic local search to provide outstanding solutions at high speed: in our experiments its performance is as good as simulated annealing, achieving an average loss with respect to the best known value of less thatï¾ź$$0.5\\,\\%$$0.5%, while its speed is comparable to the greedy algorithms.
Year
DOI
Venue
2017
10.1007/978-3-319-38851-9_17
ACM Journal of Experimental Algorithmics
DocType
Volume
ISSN
Journal
22
0302-9743
Citations 
PageRank 
References 
4
0.40
19
Authors
2
Name
Order
Citations
PageRank
Matthias Poloczek1536.39
David P. Williamson23564413.34