Омские научные чтения - 2018 - Математика

Оценивание точности жадного алгоритма для индивидуальной задачи о покрытии

Пролубников А. В.

Аннотация

Модифицируя подход, дающий логарифмическую оценку точности для жадного алгоритма решения задачи о покрытии, мы получаем оценку точности жадного алгоритма для индивидуальной задачи о покрытии. Мы показываем, что для большой доли индивидуальных задач получаемая нами оценка оказывается существенно лучше, чем логарифмическая оценка точности.

Комментарии

Комментарии отсутствуют

Вопросы по докладу

Вопросы отсутствуют