Approximation Algorithms for Discrete Polynomial Optimization

摘要：

　　We consider approximation algorithms for optimizing a generic multi-variate 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 these models, and establish the approximation ratios (or relative approximation ratios whenever appropriate) for the proposed algorithms.

关键词： polynomial function optimization binary integer programming mixed integer programming approximation algorithm approximation ratio

作者: Simai HE Zhening LI Shuzhong ZHANG

作者单位: City University of Hong Kong, Kowloon Tong, Hong Kong The Chinese University of Hong Kong, Shatin, Hong Kong

会议类型: 国际会议

会议名称: 第8届国际最优化方法及应用大会

会议地点: 上海

会议语种:英文

页码: 193-194

在线出版日期: 2010-12-10（万方平台首次上网日期，不代表论文的发表时间）