|
Дискретная математика, 1991, том 3, выпуск 3, страницы 66–72
(Mi dm805)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
О компактном суммировании векторов
С. В. Севастьянов
Аннотация:
Пусть $\{x_1,\dots,x_n\}$ – конечное множество векторов в $\mathbb R^m$, $x_1+\dots+x_n=0$ и $B=\mathrm{conv}\{x_1,\dots,x_n\}$ – выпуклая оболочка этого множества. Ранее было установлено, что существует такая перестановка $\pi=(\pi_1,\dots,\pi_n)$, что
$$
\sum_{i=1}^{n}x_{\pi_i}\in mB, \quad k=1,\dots,n.
$$
В работе показано, что суммирование векторов возможно внутри тела меньшего бъема: для любого вектора $a\in\mathbb R^m$ строится такая перестановка $\pi=(\pi_1,\dots,\pi_n)$, что
$$
\sum_{i=1}^{n}x_{\pi_i}\in (m-1)B+B_a, \quad k=1,\dots,n,
$$
где $B_a=\mathrm{conv}\{0,a-\frac1mB\}$. Конструктивно находится такой вектор $a\in\mathbb R^m$, что $(m-1)B+B_a\subseteq mB$. Перестановка $\pi$ находится алгоритмом трудоемкости $O(m^2n^2)$.
Статья поступила: 20.04.1990
Образец цитирования:
С. В. Севастьянов, “О компактном суммировании векторов”, Дискрет. матем., 3:3 (1991), 66–72
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm805 https://www.mathnet.ru/rus/dm/v3/i3/p66
|
|