首页|On some similarity of finite sets (and what we can say today about certain old problem)
On some similarity of finite sets (and what we can say today about certain old problem)
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
The paper presents a new way of classifying numerical sets (division into abstraction classes, called cuts hereafter in this paper) after imposing a constraint on the sum of elements of their subsets. A simple and not too expensive operation of sorting a set (with maximum n log(n), sorting by merge sort) allowed to determine pairs of subsets (which shall be described in the paper as pairs in a solid compound) representing a given set with the accepted constraint, which in turn allowed to prove various properties and limit the number of necessary comparisons. Then, the properties of the ratio of the sum of elements to the constraint within its cut were demonstrated, and to this cut (the abstraction class) an interval on the real number axis was assigned. To illustrate the obtained results, a mutation tree is used as an image of a unit hypercube. For introduced concepts, for example, their application for the classical number partitioning problem is shown, which is NPcomplete according to the classification (which was proved by Richard Karp in 1972 in his work [1] and classified it as a subproblem of the knapsack problem). (C) 2022 Elsevier Inc. All rights reserved.
NSTL
Elsevier
