|
Дискретный анализ и исследование операций, 2010, том 17, выпуск 6, страницы 56–67
(Mi da630)
|
|
|
|
О задаче компактного суммирования векторов внутри минимальной полосы
А. С. Козлов Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия
Аннотация:
Предложена новая задача компактного суммирования векторов. В качестве области суммирования рассматривается замкнутая полоса нефиксированного направления на плоскости. Цель – найти минимальную величину $\rho$ такую, что для любого ограниченного и уравновешенного семейства векторов существует полоса ширины $\rho$, внутри которой можно просуммировать это семейство векторов. Задача рассмотрена в трёх вариантах: строгом, нестрогом и $k$-нестрогом. В строгом случае запрещён выход частичных сумм за пределы области суммирования, в нестрогом случае запрещён выход двух подряд идущих частичных сумм, в $k$-нестрогом – выход $k+1$ подряд идущих частичных сумм. Получены первоначальные нетривиальные оценки для минимальной ширины полосы в каждом из трёх вариантов: $1\le\rho\le\frac32$, $\frac12\le\rho_{ns}\le1$ и $\frac1{k+1}\le\rho_k\le\frac12$ при $k\ge2$ соответственно. Ил. 2, библиогр. 24.
Ключевые слова:
суммирование векторов в полосе, компактное суммирование, нестрогое суммирование, эффективный алгоритм.
Статья поступила: 16.06.2010 Переработанный вариант: 28.08.2010
Образец цитирования:
А. С. Козлов, “О задаче компактного суммирования векторов внутри минимальной полосы”, Дискретн. анализ и исслед. опер., 17:6 (2010), 56–67
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da630 https://www.mathnet.ru/rus/da/v17/i6/p56
|
|