Submodular Max-SAT
Submodular Max-SAT
复制标题
DOI：
10.1007/978-3-642-23719-5_28
复制
发表时间：
2011-09
期刊：
影响因子：
--
通讯作者：
Y. Azar;Iftah Gamzu;R. Roth
中科院分区：
文献类型：
--
作者：
Y. Azar;Iftah Gamzu;R. Roth
我们介绍了次模Max-SAT问题。该问题是经典Max-SAT问题的自然推广，其中添加剂的目标函数被替换为一个子模。我们开发了一个随机线性时间2/3近似算法的问题。我们的算法是适用的，即使是在线的问题的变种。我们还建立了在线和离线设置的硬度结果。值得注意的是，对于在线设置，硬度结果证明我们的算法是最好的，而对于离线设置，硬度结果建立了经典Max-SAT和子模块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.