# Tag Info

Accepted

### How "hard" is it to maximize a polynomial function subject to linear constraints?

Your problem is NP-hard, even for polynomials of degree 2. The crucial reference is Theodore Motzkin and Ernst Strauss (1965) "Maxima for graphs and a new proof of a theorem of Turan" ...
• 5,722
Accepted

### Is there a counterexample to this work?

Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first ...
• 5,722
Accepted

### Intuitively, why is the complementary slackness condition true?

As you have noted, complementary slackness follows immediately from strong duality, i.e., equality of the primal and dual objective functions at an optimum. Complementarity slackness can be thought of ...
• 1,713
Accepted

### Why is complementary slackness important?

Complementary slackness is key in designing primal-dual algorithms. The basic idea is: Start with a feasible dual solution $y$. Attempt to find primal feasible $x$ such that $(x, y)$ satisfy ...

### Finding the sparsest solution to a system of linear equations

Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$ Take an instance of ...
• 2,295
Accepted

### Checking equivalence of two polytopes

I cannot say for sure if you will consider the following approach as better, but from a complexity-theoretic point of view there is a more efficient solution. The idea is to rephrase your question in ...
I find the geometric interpretation useful. Say we have the primal as $\max c x$ subject to $Ax \le b$ and $x \ge 0$. We know that optimum solutions are vertices of the polytope defined by the ...