RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 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.

Ключевые слова: суммирование векторов в полосе, компактное суммирование, нестрогое суммирование, эффективный алгоритм.

УДК: 519.146

Статья поступила: 16.06.2010
Переработанный вариант: 28.08.2010



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


© МИАН, 2024