Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization
From MaRDI portal
Publication:2897307
DOI10.1007/978-1-4614-1927-3_16zbMath1242.90191arXiv0909.0808OpenAlexW1828856524MaRDI QIDQ2897307
Pablo A. Parrilo, Peter N. Malkin, Jesús A. De Loera
Publication date: 10 July 2012
Published in: Mixed Integer Nonlinear Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0909.0808
semidefinite programmingcombinatorial optimizationstable setspositivstellensatzreal algebrasemi-algebraic setsgraph colorabilityMax-cutnullstellensatzlarge-scale linear algebrapolynomial equations and inequalities
Related Items
A geometrical characterization of proportionally modular affine semigroups, Positive Plücker tree certificates for non-realizability, Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz, A Polyhedral Characterization of Border Bases, Douglas-Rachford splitting and ADMM for pathological convex optimization, On the Feasibility of Semi-algebraic Sets in Poisson Regression, A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- Semidefinite representations for finite varieties
- Solving polynomial systems via symbolic-numeric reduction to geometric involutive form
- Semidefinite characterization and computation of zero-dimensional real radical ideals
- Stable sets and polynomials
- The hardest constraint problems: A double phase transition
- Semidefinite programming relaxations for semialgebraic problems
- Characterizations of border bases
- Solving polynomial equations. Foundations, algorithms, and applications
- Recognizing graph theoretic properties with polynomial ideals
- Efficient decomposition of associative algebras over finite fields
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Stable normal forms for polynomial system solving
- Another look at graph coloring via propositional satisfiability
- A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
- Global Optimization with Polynomials and the Problem of Moments
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- Theta Bodies for Polynomial Ideals
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
- Class of global minimum bounds of polynomial functions
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Using Algebraic Geometry
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Sharp Effective Nullstellensatz
- Numerical Polynomial Algebra
- Semidefinite Programming
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- GloptiPoly
- Random Graphs
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Complexity of Null- and Positivstellensatz proofs
