Minimal achievable approximation ratio for MAX-MQ in finite fields

doi:10.1016/j.tcs.2009.02.003

CSpace > 系统科学研究所

	Minimal achievable approximation ratio for MAX-MQ in finite fields
	Zhao, Shang-Wei; Gao, Xiao-Shan
	2009-05-17
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	410 期号:21-23 页码:2285-2290
摘要	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.
关键词	Multivariate quadratic polynomial equations MAX-MQ Approximation algorithm Approximation ratio
DOI	10.1016/j.tcs.2009.02.003
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000266178200031
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/9094
专题	系统科学研究所
通讯作者	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.