Get the latest tech news

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. The highest or lowest value of a linear objective function occurs at one of the vertices of this convex region, and finding it is relatively fast, depending only polynomially on the dimension n(the number of variables). Get Involved By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Get the Android app