HackerPapers

arXiv:0909.0808math.OC

Computation with Polynomial Equations and Inequalities arising in Combinatorial Optimization

Jesus A. De Loera, Peter N. Malkin, Pablo A. Parrilo

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.

arXiv comments
28 pages, survey paper
Journal reference
IMA Volumes in Mathematics and its Applications, 2012, Volume 154, Part 7, 447-481
DOI
doi:10.1007/978-1-4614-1927-3_16
Subjects
math.OCOptimization and Control math.ACCommutative Algebra

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 1 thread, from Jan 2010 to Jan 2010.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. MIT develops algorithms to "solve" non-linear systems as sum of squares 2 comments

    • His publications are here: http://www.mit.edu/~parrilo/pubs/index.html. This one in particular: http://arxiv.org/pdf/0909.0808v1 looks like it might be related.

      sspView on HNParent context

    • Can't open file from http://arxiv.org/pdf/0909.0808v1 evince says "Permission Denied". Could someone provide another link? Thanks in advance.

      gttView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.