Аппроксимация оптимумов целочисленных программ типа покрытия–упаковки

Рассматривается задача оценки величины оптимумов так называемых целочисленных программ типа покрытия–упаковки, которые содержат ограничения типа покрытия и типа упаковки одновременно. Введено понятие $\delta$-релаксации таких программ и показано, что вероятностное округление позволяет получить простые достаточные условия для точной аппроксимации целочисленных оптимумов через оптимумы $\delta$-релаксаций. Предложен эффективный вероятностный алгоритм нахождения приближенного решения целочисленных программ типа покрытия–упаковки и отмечено, что с помощью известной техники дерандомизации этот алгоритм может быть преобразован в детерминированный алгоритм.
Работа выполнена при поддержке Svenska Instituten и Российского фонда фундаментальных исследлваний, грант 99–01–00210.