Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	张国川教授，浙江大学
Inviter:
Title:	Deal with ILP with block structures: go hiking with Papadimitriou and Lenstra
Time & Venue:	2022.05.18 15:00 - 16:00 腾讯会议 215-936-919
Abstract:	Most classical combinatorial optimization problems can be modeled as integer linear programs. Basically, the hardness of an integer program is mainly determined by the size and the structure of its constraint matrix. It is well-known that the problem can be solved in (pseudo-) polynomial time if the number of variables or the number of constraints is fixed owing to the seminal work of Papadimitriou (1981) and Lenstra (1983), respectively. To move forward one needs to seek the specific structure of the constraint matrix. In recent years, an integer programming with special block structure, called the generalized 4-block n-fold IP, attracts a lot of attention, on which the existence of FPT algorithms remains a challenging question. In this talk we will present new results towards resolving this open problem. (Jointly with Hua Chen and Lin Chen)