论文标题
用于一些放松的子集总和与实数的多项式算法
A Polynomial Algorithm for Some Relaxed Subset Sum Problems with Real Numbers
论文作者
论文摘要
在本文中，我们研究了用实数的子集总和问题。从给定的问题开始，我们在polytope p上制定了一个二次最大化问题，最终将其写入距离上固定点的距离最大化。接下来，从获得的多面体开始，我们构建了一个球的相交，其中包括多层室，并表明，如果子集总和问题具有解决方案，我们可以通过最大化球上固定点的距离来找到它。也就是说，我们表明，最大化固定点上固定点的点是相同的点，可以最大程度地提高球的固定点的距离。对于后一个问题，我们给出了一个原始结果，该结果允许表征最佳点，如下所示：在球的中心和所述固定点，我们形成了一个函数，将其级别的集合是多面体。因此，我们获得了一个统一参数。 We show that by increasing this parameter from 0 to a finite maximum value (which is computed through a convex optimization problem), the polytopes in the family evolve from initially containing the intersection of balls towards three possible outcomes: a) included in the interior of the intersection of balls b) included in the interior of the complementary of the intersection of balls c) the border of the intersection of balls and the polytope of maximum parameter share至少一个点。然后，我们表明，球的交点上固定点的最大距离是由a）多型进入球的交点的最小参数，b）最大的参数与该参数仍然与球的相交点共享球的相交点c）c）参数的最大值。 ...
In this paper we study the subset sum problem with real numbers. Starting from the given problem, we formulate a quadratic maximization problem over a polytope, P, which is eventually written as a distance maximization to a fixed point over the polytope. Next, starting from the obtained polytope, we construct an intersection of balls which includes the polytope and show that in case the subset sum problem has a solution we can find it by maximizing the distance to the fixed point over the intersection of balls. That is, we show that the points which maximize the distance to the fixed point over the polytope are the same points which maximize the distance to the fixed point over the constructed intersection of balls. For the latter problem we give an original result which allows the characterization of the optimum points as follows: with the centers of the balls and the said fixed point we form a function whom sublevel sets are polytopes. As such we obtain a uni-parameter, family of polytopes. We show that by increasing this parameter from 0 to a finite maximum value (which is computed through a convex optimization problem), the polytopes in the family evolve from initially containing the intersection of balls towards three possible outcomes: a) included in the interior of the intersection of balls b) included in the interior of the complementary of the intersection of balls c) the border of the intersection of balls and the polytope of maximum parameter share at least a point. Then we show that the maximum distance to the fixed point over the intersection of balls is given by a) the smallest parameter for which the polytopes enter the intersection of balls, b) the largest parameter for which the polytopes still share points with the intersection of balls c) the maximum value of the parameter. ...
