Loading Events
  • This event has passed.
Stochastics and Statistics Seminar

Integer Feasibility of Random Polytopes

March 7, 2014 @ 11:00 am

Karthekeyan Chandrasekaran (Harvard)


Optimization problems are ubiquitous in contemporary engineering. A principal barrier to solving several real-world optimization problems is input uncertainty. In this talk, I will present new tools to study probabilistic instances of integer programs. As an application, I will show a phase-transition phenomenon in a simple distribution model for random integer programs. Our main tool is an elementary connection between integer programming and matrix discrepancy. I will describe this connection and derive matching upper and lower bounds on the discrepancy of random Gaussian matrices.
Based on joint work with Santosh Vempala.

MIT Statistics + Data Science Center
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139-4307