Minimal achievable approximation ratio for MAX-MQ in finite fields

作     者：Zhao, Shang-Wei Gao, Xiao-Shan 

作者机构：Chinese Acad Sci AMSS Key Lab Math Mechanizat Inst Syst Sci Beijing 100864 Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2009年第410卷第21-23期

页      面：2285-2290页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Key Basic Research Project of China National Natural Science Foundation of China, NSFC 

主　　题：Multivariate quadratic polynomial equations MAX-MQ Approximation algorithm Approximation ratio 

摘      要：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.