You are here

Researchers Approach New Speed Limit for Seminal Problem

Submitted by Rose Choi on January 30, 2024 - 1:27pm
Integer Linear Programming by Kristina Armitage-Lede
Kristina Armitage/Quanta Magazine

Integer linear programming can help find the answer to a variety of real-world problems. Now researchers have found a much faster way to do it. Thomas Rothvoss, in collaboration with Victor Reis of the Institute for Advanced Study, published their paper The Subspace Flatness Conjecture and Faster Integer Programming which received a best-paper award at the 2023 Foundations of Computer Science conference where they combine geometric tools to limit the possible solutions creating a newer, faster algorithm for solving ILP in almost the same time as the trivial binary case.

Full article at Quanta Magazine

People Involved: