Zobrazeno 1 - 10
of 25
pro vyhledávání: '"V. V. Shenmaier"'
Autor:
V. V. Shenmaier
Publikováno v:
Theoretical Computer Science. 818:60-73
The problem is, given a set of n vectors in a d-dimensional normed space, find a subset with the largest length of the sum vector. We prove that, in the case of the l p norm, the problem is APX-complete for any p ∈ [ 1 , 2 ] and is not in APX if p
Autor:
V. V. Shenmaier
Publikováno v:
Proceedings of the Steklov Institute of Mathematics. 307:142-150
A cycle cover of a graph is a spanning subgraph whose connected components are simple cycles. Given a complete weighted directed graph, consider the intractable problem of finding a maximum-weight cycle cover which satisfies an upper bound on the num
Publikováno v:
Proceedings of the Steklov Institute of Mathematics. 303:136-145
We consider the intractable problem of partitioning a finite set of points in Euclidean space into two clusters with minimum sum over the clusters of weighted sums of squared distances between the elements of the clusters and their centers. The cente
Autor:
V. V. Shenmaier
Publikováno v:
Mathematical Optimization Theory and Operations Research ISBN: 9783030586560
We consider the following concept. A set C in multidimensional real space is said to be a \((1+\varepsilon )\)-collection for a set X if C contains a \((1+\varepsilon )\)-approximation of every point of space with respect to the Euclidean distances t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f3e19a485aa787c4ff48ccf757ad3369
https://doi.org/10.1007/978-3-030-58657-7_10
https://doi.org/10.1007/978-3-030-58657-7_10
Autor:
V. V. Shenmaier, V. I. Khandeev, Artem V. Pyatkin, S. A. Khamidullin, Alexander Kel'manov, Yu. V. Shamardin
Publikováno v:
Pattern Recognition and Image Analysis. 28:363-370
We analyze the mathematical aspects of the data analysis problem consisting in the search (selection) for a subset of similar elements in a group of objects. The problem arises, in particular, in connection with the analysis of data in the form of ti
Autor:
V. V. Shenmaier
Publikováno v:
Computational Mathematics and Mathematical Physics. 58:850-857
The problem under study is, given a finite set of vectors in a normed vector space, find a subset which maximizes the norm of the vector sum. For each $${{\ell }_{p}}$$ norm, $$p \in [1,\infty )$$ , the problem is proved to have an inapproximability
Autor:
V. V. Shenmaier
Publikováno v:
Journal of Applied and Industrial Mathematics. 11:584-593
We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(nd−1(d + logn)). In partic
Autor:
Sergey A. Khamidullin, Artem V. Pyatkin, Alexander Kel'manov, Alexander A. Ageev, V. V. Shenmaier
Publikováno v:
Pattern Recognition and Image Analysis. 27:365-370
The work considers the mathematical aspects of one of the most fundamental problems of data analysis: search (choice) among a collection of objects for a subset of similar ones. In particular, the problem appears in connection with data editing and c
Publikováno v:
Proceedings of the Steklov Institute of Mathematics. 295:47-56
We consider the strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given cardinalities under the minimum criterion for the sum over the clusters of the intracluster sums of squared distances from e
Autor:
V. V. Shenmaier
Publikováno v:
Discrete Optimization. 22:312-327
In the incremental version of the k -median problem, we find a sequence of facility sets F 1 ⊆ F 2 ⊆ ⋯ ⊆ F n , where each F k contains at most k facilities. This sequence is said to be δ -competitive if the cost of each F k is at most δ tim