Том 17, номер 6, 2010 г., Стр. 56-67

УДК 519.146
Козлов А. С.
О задаче компактного суммирования векторов внутри минимальной полосы

Аннотация:
Предложена новая задача компактного суммирования векторов. В качестве области суммирования рассматривается замкнутая полоса нефиксированного направления на плоскости. Цель – найти минимальную величину $\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.

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

Козлов Александр Сергеевич ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: alexandr_kozlov@ngs.ru

Статья поступила 16 июня 2010 г.
Исправленный вариант — 28 августа 2010 г.