RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 1991, том 3, выпуск 3, страницы 66–72 (Mi dm805)

Эта публикация цитируется в 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)$.

УДК: 519.1, 514.17

Статья поступила: 20.04.1990



Реферативные базы данных:


© МИАН, 2024