An Interior-Point Approach to NP-Complete Problems

In the context of linear programming algorithms, we have discovered a method of making good spherical approximation of polytopes. While the problem of optimizing a quadratic function over a polytope is NP-compete; the corresponding problem can be done in polynomial-time when the search region is a sphere. We will outline an approach to solving NP-complete problems based on solutions to a sequence of quadratic optimization problems over inscribed spheres. Unlike linear programming, the potential function associated with the quadratic problem can have local minima in the interior of the polytope. When such a minimum is encountered, we transform the polytope by adding an i inequality. The number of local minima encountered was surprisingly small when we solved some difficult test problems, including the Fulkerson- Avis problems of finding the minimum width of a steiner-triple system and the maximum independent set problem for dense random graphs. :