Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials

作者：Chen Zhixiang^*; Fu Bin

来源：Journal of Combinatorial Optimization, 2013, 25(2): 234-254.

DOI：10.1007/s10878-012-9496-5

• Multivariate polynomials
• Monomial testing
• Monomial coefficient computing
• Maximum multilinear monomials
• Approximation algorithms
• Inapproximability

This paper is our third step towards developing a theory of testing monomials in multivariate polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a I I I pound polynomial. We first prove that the first problem is #P-hard and then devise a O (au)(3 (n) s(n)) upper bound for this problem for any polynomial represented by an arithmetic circuit of size s(n). Later, this upper bound is improved to O (au)(2 (n) ) for I I I pound polynomials. We then design fully polynomial-time randomized approximation schemes for this problem for I I pound polynomials. On the negative side, we prove that, even for I I I pound polynomials with terms of degree a parts per thousand currency sign2, the first problem cannot be approximated at all for any approximation factor a parts per thousand yen1, nor "weakly approximated" in a much relaxed setting, unless P=NP. For the second problem, we first give a polynomial time lambda-approximation algorithm for I I I pound polynomials with terms of degrees no more a constant lambda a parts per thousand yen2. On the inapproximability side, we give a n ((1-I mu)/2) lower bound, for any I mu > 0, on the approximation factor for I I I pound polynomials. When terms in these polynomials are constrained to degrees a parts per thousand currency sign2, we prove a 1.0476 lower bound, assuming P not equal NP; and a higher 1.0604 lower bound, assuming the Unique Games Conjecture.

• 出版日期2013-2