|
Diskretnyi Analiz i Issledovanie Operatsii, 2010, Volume 17, Issue 6, Pages 56–67
(Mi da630)
|
|
|
|
On compact vector summation within minimal strip
A. S. Kozlov S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
Abstract:
This work proposes a new problem of compact vector summation on the plane. Here the summation domain is a closed strip of unfixed direction. The goal is to find the minimal value $\rho$ such that, for an arbitrary finite family of vectors on the plane with the norm of each vector at most 1 and with the total sum equal to zero, there exists a strip of width $\rho$ such that the given vector family can be summed (in some order) within it. Three variants of the problem are considered: strict, nonstrict, and $k$-nonstrict. In the strict case, it is forbidden for partial sums to leave the strip. In the nonstrict case, it is forbidden for any two consecutive partial sums to leave the strip. In the case of $k$-nonstrict summation, it is forbidden for any $k+1$ consecutive partial sums to leave the strip. For each of the above three cases we obtain nontrivial bounds on the values of the objective function: $1\le\rho\le\frac32$, $\frac12\le\rho_{ns}\le1$, and $\frac1{k+1}\le\rho_k\le\frac12$, where $k\ge2$. Il. 2, bibliogr. 24.
Keywords:
vector summation within strip, compact vector summation, nonstrict vector summation, efficient algorithm.
Received: 16.06.2010 Revised: 28.08.2010
Citation:
A. S. Kozlov, “On compact vector summation within minimal strip”, Diskretn. Anal. Issled. Oper., 17:6 (2010), 56–67
Linking options:
https://www.mathnet.ru/eng/da630 https://www.mathnet.ru/eng/da/v17/i6/p56
|
Statistics & downloads: |
Abstract page: | 353 | Full-text PDF : | 98 | References: | 28 | First page: | 5 |
|