An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
The problem of minimizing a polynomial over the standard simplex is one of the basic NP-hard nonlinear optimization problems — it contains the maximum clique problem in graphs as a special case. It is known that the problem allows a polynomial-time approximation scheme (PTAS) for polynomials of fixed degree, which is based on polynomial evaluations … Read more