IEOR 8100

Course Information

Course Description

Linear Programming (LP) is a cornerstone of optimization theory, with a rich history and ongoing progress. This course will survey recent breakthroughs in various LP problems, many of which resolve decades-old questions. These advances have garnered multiple Best Paper Awards at premier theoretical computer science venues. Despite such progress, the quest for a strongly polynomial-time algorithm for general LP remains unresolved. We will examine the latest milestones toward this goal, as well as the roadblocks that persist.

Single-Source Shortest Paths

For graphs with nonnegative edge weights, Dijkstra’s algorithm is among the first taught in any combinatorial optimization course. While it has long been considered asymptotically optimal when paired with specialized data structures, a recent breakthrough has shown it to be truly optimal under very mild assumptions. For a broader discussion, see popular science coverage in major publications.

Our course will begin with negative edge-weights, where near-optimality was open for a very long time, and it was only very recently settled in another breakthrough result. It shows that a highly-accurate solution can be found in nearly-linear time. The techniques are self-contained, and we will cover the main approach in class. At the same conference, a shared best paper demonstrated that the more general minimum cost flow problem can be solved in almost linear time. If time permits, we will cover the high-level ideas of their algorithm.

The next major improvement, which also received a notable award, occurred in the regime where, for SSSP, we aim to transform a highly accurate algorithm into an exact one. This is akin to the distinction between weakly polynomial and strongly polynomial algorithms. Even after the breakthrough results in 2022, the fastest exact algorithm for solving SSSP remained the over half-century-old classic algorithms by Moore and Bellman-Ford. Just last year, Fineman surpassed these results. We will also cover a recent improvement and simplification, which is set to appear soon.

Generalized Shortest Paths

Beyond Single-Source Shortest Paths, a natural class can also be formulated as a linear program, preserving the graph structure. This class corresponds to sets of inequalities involving at most 2 variables. We will teach algorithms that solve these problems in strongly polynomial time.

Surprisingly, primal feasibility took several decades longer to be fully resolved. An accessible combinatorial algorithm now exists, and we will present the main ideas of its approach.

These combinatorial methods, however, do not extend to solve optimization problems over such systems. It required continuous optimization techniques to finally resolve the problem. We will present that algorithm in the second part of the course, which focuses more generally on breakthrough results achieved with continuous optimization techniques.

General Linear Programs

General Linear Programs have been known to be weakly polynomially solvable since the development of the ellipsoid method and the introduction of interior point methods. However, it is only in recent years that conditionally optimal running times have been achieved, first with a randomized approach, followed by a deterministic one. These algorithms have since been simplified, and we will teach a more accessible variant.

In a widely used framework—though restricted to certain settings—approximate algorithms can be converted into exact algorithms using randomization and proximity techniques. We will also cover a classical algorithm that efficiently solves LPs in low dimensions with only mild dependence on the number of constraints.

Finally, we will present a near-universal Interior Point Method, which finds an exact optimal solution rather than an approximate one. We will quantify its performance and show that it runs in strongly polynomial time for many classical LP problems. Moreover, we will show that this method provides the first strongly polynomial algorithm for the minimum-cost generalized flow problem.

Target Audience

PhD students in Operations Research, Computer Science, and related fields. Only basic knowledge of algorithms and linear programming is assumed. For the results we cover, we aim to provide a mostly self-contained introduction to the necessary background.

Tentative Schedule

Grading

The overall grade will consist of the following components: