Метрические аспекты теории целочисленного линейного программирования

Получены точные оценки отношения оптимумов прямой и двойственной целочисленных программ в худшем случае, а также аналогичные оценки для отношения целочисленных и рациональных оптимумов линейных программ. Показано, что в случае неотрицательных исходных данных эти отношения линейны по числу переменных и максимуму модуля исходных данных, а в общем случае могут быть экспоненциальными. Найдены также достаточные условия, гарантирующие асимптотическое равенство целочисленного и рационального оптимумов при числе переменных, стремящемся к бесконечности. Полученные результаты дают ответ на ряд вопросов, поставленных в [3, 4].
Работа выполнена при поддержке Российского фонда фундаментальных исследований, грант 93–012–459.