Об одном алгоритме решения $m$-мерной задачи о ранце со случайными коэффициентами

Исследуются вероятностные свойства алгоритма решения т-мерной задачи о ранце со случайными коэффициентами, имеющего линейную по размерности трудоемкость. Алгоритм получает оптимальное решение задач с “возмущенными” правыми частями ограничений. При росте размерности относительное возмущение стремится по вероятности к 0. При соответствующем выборе управляющих параметров алгоритм получает $\varepsilon$-оптимальное решение с вероятностью, стремящейся к 1 при росте размерности.