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,.
|
|
|