On compact vector summation within minimal strip

A. S. Kozlov

Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 6, pp. 56-67.

Résumé

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.

Détail

Keywords: vector summation within strip, compact vector summation, nonstrict vector summation
Mots-clés : efficient algorithm.

Bibliographie

[1] Belov I. S., Stolin Ya. N., “Algoritm v odnomarshrutnoi zadache kalendarnogo planirovaniya”, Matematicheskaya ekonomika i funktsionalnyi analiz, Nauka, M., 1974, 248–257 | MR

[2] Grinberg V. S., Sevastyanov S. V., “Znachenie konstanty Shteinitsa”, Funktsion. analiz i ego pril., 14:2 (1980), 56–57 | MR | Zbl

[3] Kadets M. I., “Ob odnom svoistve vektornykh lomanykh v $n$-mernom prostranstve”, Uspekhi mat. nauk, 8:1 (1953), 139–143 | MR | Zbl

[4] Sevastyanov S. V., “Ob asimptoticheskom podkhode k nekotorym zadacham teorii raspisanii”, Upravlyaemye sistemy, 14, 1975, 40–51

[5] Sevastyanov S. V., “O priblizhennom reshenii nekotorykh zadach teorii raspisanii”, Metody diskret. analiza, 32, 1978, 66–75 | MR | Zbl

[6] Sevastyanov S. V., “Algoritmy s otsenkami dlya zadach Dzhonsona i Akersa–Fridmana v sluchae trekh stankov”, Upravlyaemye sistemy, 22, 1988, 51–57

[7] Sevastyanov S. V., “Teorema o kompaktnom summirovanii vektorov v dvumernom prostranstve”, Metody diskret. analiza, 47, 1988, 61–65 | MR

[8] Sevastyanov S. V., “Geometriya v teorii raspisanii”, Modeli i metody optimizatsii, Tr. AN SSSR. Sib. otd-nie. In-t matematiki, 10, Nauka, Novosibirsk, 1988, 226–261 | MR

[9] Sevastyanov S. V., “O kompaktnom summirovanii vektorov”, Diskret. matematika, 3:3 (1991), 66–72 | MR | Zbl

[10] Sevastyanov S. V., “Nestrogoe summirovanie vektorov na ploskosti i ego primenenie v zadachakh teorii raspisanii”, Diskret. analiz i issled. operatsii. Ser. 1, 2:2 (1995), 69–100 | MR | Zbl

[11] Avgustinovich S. V., Sevast'janov S. V., “Vector summation within minimal angle”, Comput. Geom., 2 (1993), 235–239 | DOI | MR | Zbl

[12] Banaszczyk W., “The Steinitz constant of the plane”, J. Reine Angew. Math., 373 (1987), 218–220 | MR | Zbl

[13] Banaszczyk W., “A note on the Steinitz constant of the Euclidean plane”, C. R. Math. Acad. Sci. Soc. R. Can., 12:4 (1990), 97–102 | MR | Zbl

[14] Banaszczyk W., “The Steinitz lemma on rearrangement of series for nuclear spaces”, J. Reine Angew. Math., 403 (1990), 187–200 | MR | Zbl

[15] Banaszczyk W., “The Steinitz lemma in $l^2_\infty$”, Period. Math. Hung., 22 (1991), 183–186 | DOI | MR | Zbl

[16] Barany I., Grinberg V. S., “A vector-sum theorem in two-dimensional space”, Period. Math. Hung., 16 (1985), 135–138 | DOI | MR | Zbl

[17] Behrend F. A., “The Steinitz–Gross theorem on sums of vectors”, Can. J. Math., 6 (1954), 108–124 | DOI | MR | Zbl

[18] Bergsröm V., “Zwei Satze über ebene Vectorpolygone”, Abhendleungen aus dem mathematischen Seminar der Hamburgischen Universität, 8, 1931, 206–214

[19] Damsteeg I., Halperin I., “The Steinitz–Gross theorem on sums of vectors”, Proc. Trans. Royal Soc. Canada Sect. III (3), 44 (1950), 31–35 | MR | Zbl

[20] Gross W., “Bedingt konvergente Reihen”, Monatsh. Math. Physik, 28 (1917), 221–237 | DOI | MR | Zbl

[21] Sevast'janov S. V., “On some geometric methods in scheduling theory: a survey”, Discrete Appl. Math., 55 (1994), 59–82 | DOI | MR

[22] Sevastianov S., “Nonstrict vector summation in multi-operation scheduling”, Ann. Oper. Res., 83 (1998), 179–211 | DOI | MR | Zbl

[23] Sevast'janov S. V., Banaszczyk W., “To the Steinitz lemma in coordinate form”, Diskrete Math., 169 (1997), 145–152 | DOI | MR

[24] Steinitz E., “Bedingt konvergente Reihen und convexe Systeme”, J. Reine Angew. Math., 143 (1913), 128–175 | Zbl