Abstract. The problem of packing identical spheres in a unit cube in n-dimensional space is considered. The dual Lagrange bound (upper bound for sphere radius) for the classical quadratic formulation of the problem and some formulations obtained by expanding it by families of functionally redundant constraints is analyzed. The analytical expression for the dual bound is obtained in the basic formulation. Refs: 19 titles.
Keywords: packing density, extremal quadratically constrained quadratic programming problem, Lagrangian dual bound, functionally redundant constraint, negatively definite matrix.
Березовский Олег Анатольевич,
кандидат физ.-мат. наук, старший научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
e-mail: berezovskyi@mail.ru.