Submodular Max-SAT

We introduce the submodular Max-SAT problem. This problem is a natural generalization of the classical Max-SAT problem in which the additive objective function is replaced by a submodular one. We develop a randomized linear-time 2/3-approximation algorithm for the problem. Our algorithm is applicable even for the online variant of the problem. We also establish hardness results for both the online and offline settings. Notably, for the online setting, the hardness result proves that our algorithm is best possible, while for the offline setting, the hardness result establishes a computational separation between the classical Max-SAT and the submodular Max-SAT.