.png){kind=icon}
返回
Differential approximation for optimal satisfiability and related problems
.png){kind=icon}
PRE
AI
DOI：10.1016/S0377-2217(02)00299-0.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We study the differential approximability of several optimization satisfiability problems. We prove that, unless co - RP = NP, MIN SAT is not differential 1/m(1-epsilon)-approximable for any epsilon > 0, where m is the number of clauses. We also prove that any differential approximation algorithm for MAX minimal vertex cover can be transformed into a differential approximation algorithm for MIN kSAT achieving the same differential performance ratio. This leads us to study the differential approximability of MAX minimal vertex cover and MIN independent dominating set. Both of them are equivalent for the differential approximation. For these problems we prove a strong inapproximability result, informally, unless P = NP, any approximation algorithm has worst-case approximation ratio equal to 0. (C) 2002 Elsevier Science B.V. All rights reserved.
Keyword:
combinatorial optimization
complexity theory
heuristics
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
暂无机构信息
引用论文
.png){kind=icon}
没有更多内容
没有更多内容