| Title: | conditional hardness of approximating satisfiable max 3csp-q |
| Author: | Tang Linqing
|
| Source: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|
| Conference Name: | 20th International Symposium on Algorithms and Computations (ISAAC 2009)
|
| Conference Date: | DEC 16-18,
|
| Issued Date: | 2009
|
| Conference Place: | Honolulu, HI
|
| Keyword: | Computer operating procedures
; Hardness
|
| Publisher: | ALGORITHMS AND COMPUTATION, PROCEEDINGS
|
| Publish Place: | HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
|
| Indexed Type: | istp,ei
|
| ISSN: | 0302-9743
|
| ISBN: | 978-3-642-10630-9
|
| Department: | Tang, Linqing Chinese Acad Sci, State Key Lab Comp Sci, Inst Software, Beijing 100080, Peoples R China.
|
| Sponsorship: | Univ Hawaii, Univ Texas Dallas
|
| English Abstract: | 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. |
| Language: | 英语
|
| Content Type: | 会议论文
|
| 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,.
|
|
|
