Why is integer programming hard?

• Time : 10:30 - 12:00 (GMT+9, KST)
  
• Speaker : Tony Huynh (IBS)
  

Integer programming is a powerful mathematical optimization model that is widely used in both practice and theory. In particular, it can be used to model many NP-hard optimization problems. Thus, we do not expect general integer programs to be solvable in polynomial time (unless P=NP).
However, a beautiful conjecture of Shevchenko from 1997 asserts that integer programs can be solved in polynomial time when all subdeterminants of the constraint matrix are bounded in absolute value by a constant. I will survey known results around this conjecture, including very recent joint work with Samuel Fiorini, Pascal Gollin, Simon Keil, O-joung Kwon, Sang-il Oum, Roohani Sharma, and Stefan Weltge. No knowledge of integer programming will be assumed.