论文标题
最大化线性形式的产物，以及阳性半金属矩阵的永久性
Maximizing Products of Linear Forms, and The Permanent of Positive Semidefinite Matrices
论文作者
论文摘要
我们研究了多项式优化问题的凸松弛，最大程度地利用了复杂球上线性形式的产物。我们表明，该凸面程序也是对遗式阳性半芬酸盐（HPSD）矩阵永久性的放松。通过分析一种建设性的随机圆形算法，我们获得了对HPSD矩阵永久性的改进的乘法近似因子，以及该近似值的计算高效证书。我们还提出了van der Waerden对HPSD矩阵的猜想的类似物，其中多项式优化问题被解释为永久性的放松。
We study the convex relaxation of a polynomial optimization problem, maximizing a product of linear forms over the complex sphere. We show that this convex program is also a relaxation of the permanent of Hermitian positive semidefinite (HPSD) matrices. By analyzing a constructive randomized rounding algorithm, we obtain an improved multiplicative approximation factor to the permanent of HPSD matrices, as well as computationally efficient certificates for this approximation. We also propose an analog of van der Waerden's conjecture for HPSD matrices, where the polynomial optimization problem is interpreted as a relaxation of the permanent.
