conditional hardness of approximating satisfiable max 3csp-q
文献类型：会议论文
| 作者 | Tang Linqing |
| 出版日期 | 2009 |
| 会议名称 | 20th International Symposium on Algorithms and Computations (ISAAC 2009) |
| 会议日期 | DEC 16-18, |
| 会议地点 | Honolulu, HI |
| 关键词 | Computer operating procedures Hardness |
| 页码 | 923-932 |
| 英文摘要 | In this article, we study the approximability of satisfiable Max 3CSP-q for q > 3 be a prime. We give a (1/q + 1/q(2) - 1/q(3)) + epsilon-hardness result for approximate Max 3CSP-q even on satisfiable instances, conditioned on Khots d-to-1 Conjecture, for any finite constant integer d < q/2. |
| 收录类别 | ISTP,EI |
| 会议主办者 | Univ Hawaii, Univ Texas Dallas |
| 会议录 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 |
| 会议录出版者 | ALGORITHMS AND COMPUTATION, PROCEEDINGS |
| 会议录出版地 | HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY |
| 语种 | 英语 |
| ISSN号 | 0302-9743 |
| ISBN号 | 978-3-642-10630-9 |
| 源URL | [http://124.16.136.157/handle/311060/8202]  |
| 专题 | 软件研究所_软件所图书馆_2009年期刊/会议论文 |
| 推荐引用方式 GB/T 7714 | Tang Linqing. conditional hardness of approximating satisfiable max 3csp-q[C]. 见:20th International Symposium on Algorithms and Computations (ISAAC 2009). Honolulu, HI. DEC 16-18,. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。