| 题名: | conditional hardness of approximating satisfiable max 3csp-q |
| 作者: | Tang Linqing
|
| 会议文集: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|
| 会议名称: | 20th International Symposium on Algorithms and Computations (ISAAC 2009)
|
| 会议日期: | DEC 16-18,
|
| 出版日期: | 2009
|
| 会议地点: | Honolulu, HI
|
| 关键词: | Computer operating procedures
; Hardness
|
| 出版者: | ALGORITHMS AND COMPUTATION, PROCEEDINGS
|
| 出版地: | HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
|
| 收录类别: | istp,ei
|
| ISSN: | 0302-9743
|
| ISBN: | 978-3-642-10630-9
|
| 部门归属: | Tang, Linqing Chinese Acad Sci, State Key Lab Comp Sci, Inst Software, Beijing 100080, Peoples R China.
|
| 主办者: | Univ Hawaii, Univ Texas Dallas
|
| 英文摘要: | 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. |
| 语种: | 英语
|
| 内容类型: | 会议论文
|
| URI标识: | http://ir.iscas.ac.cn/handle/311060/8202
|
| Appears in Collections: | 中科院软件所图书馆_2009年期刊/会议论文
|
|
There are no files associated with this item.
|
| Recommended Citation: | |
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,.
|
|
|
