Approximation Algorithms for Discrete Polynomial Optimization

  • PDF / 1,044,728 Bytes
  • 34 Pages / 439.37 x 666.142 pts Page_size
  • 89 Downloads / 238 Views

DOWNLOAD

REPORT


Approximation Algorithms for Discrete Polynomial Optimization Simai He · Zhening Li · Shuzhong Zhang

Received: 19 December 2012 / Accepted: 22 December 2012 / Published online: 20 February 2013 © Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg 2013

Abstract 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. Keywords Polynomial optimization problem · Binary integer programming · Mixed integer programming · Approximation algorithm · Approximation ratio Simai He was 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) and 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). S. He Department of Management Sciences, City University of Hong Kong, Kowloon, Hong Kong e-mail: [email protected] Z. Li () Department of Mathematics, Shanghai University, Shanghai 200444, China e-mail: [email protected] S. Zhang Department of Industrial & Systems Engineering, University of Minnesota, Minneapolis, MN 55455, USA e-mail: [email protected]

4

S. He et al.

Mathematics Subject Classification 90C10 · 90C11 · 90C59 · 15A69 · 90C26

1 Introduction This paper is concerned with optimizing a (high degree) multivariate polynomial function in (mixed) binary variables. Our basic model is to maximize a d-th degree polynomial function p(x) where x = (x1 , x2 , · · · , xn )T is chosen such that xi ∈ {1, −1} for i = 1, 2, · · · , n. For ease of referencing, let us call this basic model to be (P ) : maxx∈{1,−1}n p(x). This type of problem can be found in a great variety of application domains. For example, the following hypergraph max-covering problem is well studied in the literature, which is precisely (P ). Given a hypergraph H = (V , E) with V being the set of vertices and E the set of hyperedges (or subsets of V ), and each hyperedge e ∈ E is associated with a real-valued weight w(e). The problem is to find a subset S of the vertices set V , such that the total weight of the hyperedges covered by S is

Data Loading...