排序方式: 共有13条查询结果,搜索用时 15 毫秒
1.
2.
A. V. Kel’manov L. V. Mikhailova S. A. Khamidullin V. I. Khandeev 《Computational Mathematics and Mathematical Physics》2017,57(8):1376-1383
We consider the problem of partitioning a finite sequence of Euclidean points into a given number of clusters (subsequences) using the criterion of the minimal sum (over all clusters) of intercluster sums of squared distances from the elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is at the origin, while the center of each of the other clusters is unknown and determined as the mean value over all elements in this cluster. Additionally, the partition obeys two structural constraints on the indices of sequence elements contained in the clusters with unknown centers: (1) the concatenation of the indices of elements in these clusters is an increasing sequence, and (2) the difference between an index and the preceding one is bounded above and below by prescribed constants. It is shown that this problem is strongly NP-hard. A 2-approximation algorithm is constructed that is polynomial-time for a fixed number of clusters. 相似文献
3.
A 2-approximation algorithm is presented for some NP-hard data analysis problem that consists in partitioning a set of Euclidean vectors into two subsets (clusters) under the criterion of minimum sum-of-squares of distances from the elements of clusters to their centers. The center of the first cluster is the average value of vectors in the cluster, and the center of the second one is the origin. 相似文献
4.
Kel’manov A. V. Panasenko A. V. Khandeev V. I. 《Computational Mathematics and Mathematical Physics》2019,59(5):842-850
Computational Mathematics and Mathematical Physics - Two strongly NP-hard problems of clustering a finite set of points in Euclidean space are considered. In the first problem, given an input set,... 相似文献
5.
Kel’manov A. V. Khamidullin S. A. Khandeev V. I. 《Computational Mathematics and Mathematical Physics》2018,58(12):2078-2085
Computational Mathematics and Mathematical Physics - We consider a strongly NP-hard problem of partitioning a finite Euclidean sequence into two clusters of given cardinalities minimizing the sum... 相似文献
6.
Doklady Mathematics - We consider the problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum, over all clusters, of the intracluster sums of the... 相似文献
7.
A. V. Kel’manov L. V. Mikhailova S. A. Khamidullin V. I. Khandeev 《Proceedings of the Steklov Institute of Mathematics》2017,296(1):88-103
We give a slight refinement to the process by which estimates for exponential sums are extracted from bounds for Vinogradov’s mean value. Coupling this with the recent works of Wooley, and of Bourgain, Demeter and Guth, providing optimal bounds for the Vinogradov mean value, we produce a powerful new kth derivative estimate. Roughly speaking, this improves the van der Corput estimate for k ≥ 4. Various corollaries are given, showing for example that \(\zeta \left( {\sigma + it} \right){ \ll _\varepsilon }{t^{{{\left( {1 - \sigma } \right)}^{3/2}}/2 + \varepsilon }}\) for t ≥ 2 and 0 ≤ σ ≤ 1, for any fixed ε > 0. 相似文献
8.
Doklady Mathematics - We consider three related problems of partitioning an $$N$$-element set of points in $$d$$-dimensional Euclidean space into two clusters balancing the value of (1) the... 相似文献
9.
A. V. Kel’manov S. A. Khamidullin V. I. Khandeev 《Journal of Applied and Industrial Mathematics》2016,10(2):209-219
We consider a strongly NP-hard problem of partitioning a finite sequence of points in Euclidean space into the two clustersminimizing the sum over both clusters of intra-cluster sums of squared distances from the clusters elements to their centers. The sizes of the clusters are fixed. The centroid of the first cluster is defined as the mean value of all vectors in the cluster, and the center of the second cluster is given in advance and equals 0. Additionally, the partition must satisfy the restriction that for all vectors in the first cluster the difference between the indices of two consequent points from this cluster is bounded from below and above by some given constants.We present a fully polynomial-time approximation scheme for the case of fixed space dimension. 相似文献
10.
Doklady Mathematics - We consider the problem of clustering a finite set of N points in d-dimensional Euclidean space into two clusters minimizing the sum (over both clusters) of the intracluster... 相似文献