Для минимизационного варианта задачи о ранце с булевыми переменными дано формальное описание прямых и двойственных "жадных" методов. Указаны связи этих методов с соответствующими методами для максимизационной задачи. Исследовано поведение в среднем прямого и двойственного методов для минимизационной задачи. Предполагается, что коэффициенты целевой функции и ограничения - независимые, одинаково распределенные на [0, 1] случайные величины с произвольным распределением, имеющим плотность, а правая часть d детерминирована и пропорциональна числу переменных, т.е. d = n. Найдено условие на , при котором прямой и двойственный жадные методы имеют асимптотическую погрешность t.
