Faster Integer Programming

Many important practical computations, such as scheduling, combinatorial, and optimization problems, use techniques known as integer programming to find the best combination of many variables. In these problems, some or all of the variables are restricted to integer values, which requires exponentially greater resources to solve than if the variables could take any value. Last year, Victor Reis, now at the Institute for Advanced Study in Princeton, NJ, and his Ph.D. advisor Thomas Rothvoss of the University of Washington, proved a new upper bound on the time required to solve for any integer program. They analyzed an algorithm described more than a decade ago in the influential Ph.D. thesis of Daniel Dadush, now in the Netherlands at CWI (the Center for Mathematics and Informatics) and Utrecht University. "In some sense the algorithm is his, but we have proven that it works," Rothvoss said.