ПОВЕДЕНИЕ В СРЕДНЕМ ЖАДНЫХ АЛГОРИТМОВ ДЛЯ МИНИМИЗАЦИОННОЙ ЗАДАЧИ О РАНЦЕ - ОБЩИЕ РАСПРЕДЕЛЕНИЯ КОЭФФИЦИЕНТОВ

摘要

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