Заседание научного семинара лаборатории ЛАТАС
Докладчик: Prof. Joseph Paat (University of British Columbia Sauder School of Business, Vancouver, Canada)
Тема: Improved Proximity Results in Integer Linear Programming
Язык семинара: English
Abstract: Perhaps the most common way to approximate an integer linear program (ILP) is to use its linear programming (LP) relaxation. In this talk, we consider the problem of bounding the largest distance between many vertex of the LP and some solution of the ILP. Focus will be placed on a canonical result of Cook et al., which shows that the largest such distance (when measured in the max-norm) can be bounded by the dimension of the problem multiplied by the largest determinant of the constraint matrix. We give the first improvement of their result in the assumption of integer-valued data defining the ILP.
Приглашаются все желающие.
Явка аспирантов школы компьютерных наук обязательна.
Чтобы получить ссылку на конференцию Zoom, необходимо зарегистрироваться.