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

Мы используем метод вероятностного округления для оценки величины оптимума программы
$$ \{\min\mathbf{cx}\mid A\mathbf x\geq\mathbf b,\mathbf x\geq\mathbf 0, \mathbf x\text{ --- целочисленный вектор}\}, $$
где $\mathbf b>\mathbf 0$, $\mathbf c\geq\mathbf 0$ — рациональные векторы и $A$ — произвольная рациональная матрица. Наша оценка обобщает некоторые известные оценки для целочисленных программ типа покрытия, то есть тех же программ с условием неотрицательности всех элементов $A$.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 02–01–00713 и 04–01–00359, и при поддержке Шведской академии наук.