Approximation Algorithms for Discrete Polynomial Optimization
Approximation Algorithms for Discrete Polynomial Optimization
复制标题
DOI：
10.1007/s40305-013-0003-1
复制
发表时间：
2013-02
影响因子：
1.4
通讯作者：
Simai He;Zhening Li;Shuzhong Zhang
中科院分区：
文献类型：
--
作者：
Simai He;Zhening Li;Shuzhong Zhang
在本文中，我们考虑近似算法优化离散（通常是二进制）变量的通用多元多项式函数。这些模型在图论、神经网络、纠错码等许多领域都有自然的应用。特别是，我们专注于三种类型的优化模型：（1）最大化一个齐次多项式函数在二进制变量;（2）最大化齐次多项式函数在二进制变量，混合变量下的球形约束;（3）最大化一个非齐次多项式函数在二进制变量。我们提出了多项式时间的随机近似算法，这样的多项式优化模型，并建立所提出的算法的近似比（或相对近似比适当时）。文中还讨论了这些模型和算法的应用实例。
In this paper, we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete (typically binary) variables. Such models have natural applications in graph theory, neural networks, error-correcting codes, among many others. In particular, we focus on three types of optimization models: (1) maximizing a homogeneous polynomial function in binary variables; (2) maximizing a homogeneous polynomial function in binary variables, mixed with variables under spherical constraints; (3) maximizing an inhomogeneous polynomial function in binary variables. We propose polynomial-time randomized approximation algorithms for such polynomial optimization models, and establish the approximation ratios (or relative approximation ratios whenever appropriate) for the proposed algorithms. Some examples of applications for these models and algorithms are discussed as well.