Minimal achievable approximation ratio for MAX-MQ in finite fields
文献类型：期刊论文
| 作者 | Zhao, Shang-Wei; Gao, Xiao-Shan
|
| 刊名 | THEORETICAL COMPUTER SCIENCE
 |
| 出版日期 | 2009-05-17 |
| 卷号 | 410期号:21-23页码:2285-2290 |
| 关键词 | Multivariate quadratic polynomial equations MAX-MQ Approximation algorithm Approximation ratio |
| ISSN号 | 0304-3975 |
| DOI | 10.1016/j.tcs.2009.02.003 |
| 英文摘要 | Given a multivariate quadratic polynomial system in a finite field F,, the problem MAX-MQ is to find a solution satisfying the maximal number of equations. We prove that the probability of a random assignment satisfying a non-degenerate quadratic equation is at least 1/q - O(q(-n/2)), where n is the number of the variables in the equation. Consequently, the random assignment provides a polynomial-time approximation algorithm with approximation ratio q + O(q(-n/2)) for non-degenerate MAX-MQ. For large n, the ratio is close to q. According to a result by Hastad, it is NP-hard to approximate MAX-MQ with an approximation ratio of q - is an element of for a small positive number is an element of. Therefore, the minimal approximation ratio that can be achieved in polynomial time for MAX-MQ is q. (C) 2009 Elsevier B.V. All rights reserved. |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000266178200031 |
| 出版者 | ELSEVIER SCIENCE BV |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/9093]  |
| 专题 | 系统科学研究所 |
| 通讯作者 | Gao, Xiao-Shan |
| 作者单位 | Chinese Acad Sci, AMSS, Key Lab Math Mechanizat, Inst Syst Sci, Beijing 100864, Peoples R China |
| 推荐引用方式 GB/T 7714 | Zhao, Shang-Wei,Gao, Xiao-Shan. Minimal achievable approximation ratio for MAX-MQ in finite fields[J]. THEORETICAL COMPUTER SCIENCE,2009,410(21-23):2285-2290. |
| APA | Zhao, Shang-Wei,&Gao, Xiao-Shan.(2009).Minimal achievable approximation ratio for MAX-MQ in finite fields.THEORETICAL COMPUTER SCIENCE,410(21-23),2285-2290. |
| MLA | Zhao, Shang-Wei,et al."Minimal achievable approximation ratio for MAX-MQ in finite fields".THEORETICAL COMPUTER SCIENCE 410.21-23(2009):2285-2290. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。