Institutional Repository
| conditional hardness of approximating satisfiable max 3csp-q | |
| Tang Linqing | |
| 2009 | |
| Conference Name | 20th International Symposium on Algorithms and Computations (ISAAC 2009) |
| Source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Pages | 923-932 |
| Conference Date | DEC 16-18, |
| Conference Place | Honolulu, HI |
| Indexed Type | istp,ei |
| Publish Place | HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY |
| Publisher | ALGORITHMS AND COMPUTATION, PROCEEDINGS |
| 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. |
| 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. |
| Keyword | Computer Operating Procedures Hardness |
| Sponsorship | Univ Hawaii, Univ Texas Dallas |
| Language | 英语 |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8202 |
| Collection | 2009年期刊/会议论文 |
| Recommended Citation GB/T 7714 | Tang Linqing. conditional hardness of approximating satisfiable max 3csp-q[C]. HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY:ALGORITHMS AND COMPUTATION, PROCEEDINGS,2009:923-932. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment