Поведение в среднем жадных алгоритмов для минимизационной задачи о ранце – общие распределения коэффициентов

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