Why is integer programming hard?
| 구분 | ACM |
|---|---|
| 일정 | 2026-12-04(금) 10:30~12:00 |
| 세미나실 | 27동 220호 |
| 강연자 | 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.