Computation with Polynomial Equations and Inequalities arising in Combinatorial Optimization
arXiv:0909.0808 · doi:10.1007/978-1-4614-1927-3_16
Abstract
The purpose of this note is to survey a methodology to solve systems of polynomial equations and inequalities. The techniques we discuss use the algebra of multivariate polynomials with coefficients over a field to create large-scale linear algebra or semidefinite programming relaxations of many kinds of feasibility or optimization questions. We are particularly interested in problems arising in combinatorial optimization.
28 pages, survey paper
References in corpus (5)
- Semidefinite Characterization and Computation of Real Radical Ideals
- Theta Bodies for Polynomial Ideals
- Stable normal forms for polynomial system solving
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz
Cited by in corpus (5)
- Douglas--Rachford Splitting and ADMM for Pathological Convex Optimization
- A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs
- A polyhedral approach to computing border bases
- A geometrical characterization of proportionally modular affine semigroups
- On the feasibility of semi-algebraic sets in Poisson regression