General Linear Programming (Linear Programming)
Jump to navigation
Jump to search
Description
Linear programming (LP; also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization).
Related Problems
Subproblem: Linear Programming with Reals
Related: Integer Linear Programming, 0-1 Linear Programming
Parameters
$n$: number of variables
$m$: number of constraints
$L$: length of input, in bits
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Fourier–Motzkin elimination | 1940 | $O((m/{4})$^{({2}^n)}) | $O((m/{4})$^{({2}^n)}) | Exact | Deterministic | |
| Khachiyan Ellipsoid algorithm | 1979 | $O(n^{6} * L^{2} \log L \log\log L)$ | $O(nmL)$ | Exact | Deterministic | Time |
| Karmarkar's algorithm | 1984 | $O(n^{3.5} L^{2} logL loglogL)$ | $O(nmL)$ | Exact | Deterministic | Time |
| Simplex Algorithm | 1947 | $O({2}^n*poly(n, m))$ | $O(nm)$ | Exact | Deterministic | |
| Terlaky's Criss-cross algorithm | 1985 | $O({2}^n*poly(n, m))$ | $O(nm)$ | Exact | Deterministic | |
| Affine scaling | 1967 | ? (originally $O(n^{3.5} L)$ but seems unclear) | $O(nm+m^{2})$? | Exact | Deterministic | |
| Cohen; Lee and Song | 2018 | $O(n^{max(omega, {2.5}-alpha/{2}, {13}/{6})}*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication;
currently $O(n^{2.37285956})$ || $O(nm+n^{2})$? || Exact || Deterministic || Time | ||||
| Lee and Sidford | 2015 | $O((nnz(A) + n^{2}) n^{0.5})$ | $O(nm+n^{2})$?? | Exact | Deterministic | Time |
| Vaidya | 1987 | $O(((m+n)$n^{2}+(m+n)^{1.5}*n)L^{2} logL loglogL) | $O((nm+n^{2})$L)? | Exact | Deterministic | Time |
| Vaidya | 1989 | $O((m+n)$^{1.5}*n*L^{2} logL loglogL) | $O((nm+n^{2})$L)? | Exact | Deterministic | Time |
| Jiang, Song, Weinstein and Zhang | 2020 | $O(n^(max(omega, {2.5}-alpha/{2}, {37}/{18}))*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication;
currently $O(n^{2.37285956})$ || || Exact || Deterministic || Time |