





















In this paper we study the problem of maximizing the distance to a given point over an intersection of balls. It was already known that this problem can be solved in polynomial time and space if the given point is not in the convex hull of the balls centers. The cases where the given point is in the convex hull of the balls centers include all NP-complete problems as we show. Some novel results are given in this area. A novel projection algorithm is developed then applied in the context of the Subset Sum Problem (SSP). Under the assumption that the SSP has at most one solution, we provide a quasi-polynomial algorithm, which decreases the radius of an initial ball containing the solution to the SSP. We perform some numerical tests which show the effectiveness of the proposed algorithm.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。