Skip to main content

Learning algorithms for linear programming

Supervisor

Suitable for

MSc in Computer Science
Computer Science, Part B
Mathematics and Computer Science, Part C
Computer Science and Philosophy, Part C
Computer Science, Part C

Abstract

Linear programming (LP) is an important algorithmic problem. There are efficient algorithms for LP, such as the Simplex Algorithm, that do not perform well in the worst case, and there are inefficient algorithms, such as the Ellipsoid Algorithm, that are good in theory but not in practice. Learning algorithms, such as the Multiplicative Weight Update Algorithm, have the potential to be good both in theory and in practice. The project will address this question with theoretical analysis and implementation.

Prerequisites: Mathematical and algorithmic maturity. Fundamentals of learning theory is useful, but not essential