Approximation algorithms for discrete polynomial optimization

DOI10.1007/s40305-013-0003-1zbMath1281.90026OpenAlexW2163718799MaRDI QIDQ384206

Zhening Li, Simai He, Shu-Zhong Zhang

Publication date: 27 November 2013

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40305-013-0003-1

zbMATH Keywords

approximation algorithmmixed integer programmingpolynomial optimization problemapproximation ratiobinary integer programming

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Nonconvex programming, global optimization (90C26) Approximation methods and heuristics in mathematical programming (90C59) Multilinear algebra, tensor calculus (15A69)

Related Items

On norm compression inequalities for partitioned block tensors, A matrix nonconvex relaxation approach to unconstrained binary polynomial programs, On the Consistent Path Problem, Approximation algorithms for optimization of real-valued general conjugate complex forms, Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems, Characterizing Real-Valued Multivariate Complex Polynomials and Their Symmetric Tensor Representations, Approximation methods for complex polynomial optimization, On the tensor spectral \(p\)-norm and its dual norm via partitions, Inhomogeneous polynomial optimization over a convex set: An approximation approach, Probability Bounds for Polynomial Functions in Random Variables

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for homogeneous polynomial optimization with quadratic constraints
• Approximation algorithms for indefinite complex quadratic maximization problems
• Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems
• ``Neural computation of decisions in optimization problems
• Quick approximation to matrices and applications
• Faster algorithms for Frobenius numbers
• Solving a System of Linear Diophantine Equations with Lower and Upper Bounds on the Variables
• On the Best Rank-1 Approximation of Higher-Order Supersymmetric Tensors
• Spectral methods for matrices and tensors
• Maximum Block Improvement and Polynomial Optimization
• Random sampling and approximation of MAX-CSP problems
• Methods of Nonlinear 0-1 Programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Neural networks, error-correcting codes, and polynomials over the binary n-cube
• Automata, Languages and Programming
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
• Approximating the Cut-Norm via Grothendieck's Inequality
• A Selection Problem of Shared Fixed Costs and Network Flows
• Notes—On a Selection Problem