Why is integer programming hard?

모드선택 :              
세미나 신청은 모드에서 세미나실 사용여부를 먼저 확인하세요

Why is integer programming hard?

김수현 0 6000
구분 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.  

    정원 :
    부속시설 :
세미나명