×

A Beck-Fiala-type theorem for Euclidean norms. (English) Zbl 0736.51011

Let \(\mathbb{R}^ n\) be provided with the euclidean norm \(\|\;\|\) and let \(D\subseteq\mathbb{R}^ n\) be an ellipsoid with centre \(O\) and principal semiaxes \(\lambda_ 1,\ldots,\lambda_ n\). For arbitrary \(m\) choose \(u_ 1,\ldots,u_ m\in D\). Then there exist \(\Theta_ 1,\ldots,\Theta_ m\in\{1,-1\}\) such that \[ \left\|\sum^ m_{i=1}\Theta_ iu_ i\right\|\leq\left(\sum^ m_{j=1}\lambda^ 2_ j \right)^{1/2}. \] This result is connected with the Beck-Fiala theorem [J. Beck and T. Fiala, Discrete Appl. Math. 3, 1-8 (1981; Zbl 0473.05046)].

MSC:

51M16 Inequalities and extremum problems in real or complex geometry

Citations:

Zbl 0473.05046
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Banaszczyk, W., The Steinitz theorem on rearrangement of series for nuclear spaces, J. Reine Angew. Math.,, 403, 187-200 (1990) · Zbl 0682.46002
[2] Beck, J.; Fiala, T., Integer-making theorems, Discr. Appl. Math.,, 3, 1-8 (1981) · Zbl 0473.05046
[3] Beck, J.; Spencer, J., Integral approximation sequences, Math. Programm.,, 30, 88-98 (1984) · Zbl 0549.41015
[4] Grinberg, V. S.; Sevastyanov, S. V., Value of the Steinitz constant, Funkt. Anal. Prilozhen, 14, 56-57 (1980), (in Russian); translated as Funct. Anal. Appl., 14 (1980), 125-126 · Zbl 0446.46009
[5] Sevastyanov, S. V., On the approximate solution of the problem of calendar planning, Upravlyaemye Systemy, No. 20, 49-63 (1980), (in Russian)
[6] Sevastyanov, S. V., Geometry in theory of scheduling. Models and methods of optimization, Trudy Inst. Math, No. 10, 226-261 (1988), Nauka, Sibirsk. Otdel., Novosibirsk (in Russian)
[7] Spencer, J., Six standard deviations suffice, Trans. Am. Math. Soc.,, 289, 679-705 (1985) · Zbl 0577.05018
[8] Spencer, J., Ten Lectures on the Probabilistic Method, (Society for Industrial and Applied Mathematics (1987)), Philadelphia, Pennysylvania · Zbl 0703.05046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.