Approximation Algorithms for Discrete Polynomial Optimization

作     者：Simai He Zhening Li Shuzhong Zhang 

作者机构：Department of Management SciencesCity University of Hong KongKowloonHong Kong Department of MathematicsShanghai UniversityShanghai 200444China Department of Industrial&Systems EngineeringUniversity of MinnesotaMinneapolisMN 55455USA 

出 版 物：《Journal of the Operations Research Society of China》 (中国运筹学会会刊（英文）)

年 卷 期：2013年第1卷第1期

页      面：3-36页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：supported in part by Hong Kong General Research Fund(No.CityU143711) Zhening Li was supported in part by Natural Science Foundation of Shanghai(No.12ZR1410100) Ph.D.Programs Foundation of Chinese Ministry of Education(No.20123108120002) Shuzhong Zhang was supported in part by U.S.National Science Foundation(No.CMMI-1161242) 

主　　题：Polynomial optimization problem Binary integer programming Mixed integer programming Approximation algorithm Approximation ratio 

摘      要：In this paper,we consider approximation algorithms for optimizing a generic multivariate polynomial function in discrete(typically binary)*** models have natural applications in graph theory,neural networks,error-correcting codes,among many *** 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 *** propose polynomial-time randomized approximation algorithms for such polynomial optimizationmodels,and establish the approximation ratios(or relative approximation ratios whenever appropriate)for the proposed *** examples of applications for these models and algorithms are discussed as well.