Theory and Applications of N-Fold Integer Programming

We overview our recently introduced theory of n-fold integer programming which enables the polynomial time solution of fundamental linear and nonlin-ear integer programming problems in variable dimension. We demonstrate its power by obtaining the first polynomial time algorithms in several application areas including multicommodity flows and privacy in statistical databases.