View source for 0-1 Linear Programming

{{DISPLAYTITLE:0-1 Linear Programming (Linear Programming)}}
== Description == 

In this case, we require all of the variables to be either 0 or 1.

== Related Problems == 

Generalizations: [[Integer Linear Programming]]

Related: [[General Linear Programming]], [[Linear Programming with Reals]]

== Parameters == 

$n$: number of variables

$m$: number of constraints

$L$: length of input, in bits

== Table of Algorithms == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Fourier–Motzkin elimination ( Linear Programming)|Fourier–Motzkin elimination]] || 1940 || $O((m/{4})$^{({2}^n)}) || $O((m/{4})$^{({2}^n)}) || Exact || Deterministic ||  
|-
| [[Khachiyan Ellipsoid algorithm  ( Linear Programming)|Khachiyan Ellipsoid algorithm ]] || 1979 || $O(n^{6} * L^{2} \log L \log\log L)$ || $O(nmL)$ || Exact || Deterministic || [https://www.sciencedirect.com/science/article/abs/pii/0041555380900610 Time]
|-
| [[Karmarkar's algorithm ( Linear Programming)|Karmarkar's algorithm]] || 1984 || $O(n^{3.5} L^{2} logL loglogL)$ || $O(nmL)$ || Exact || Deterministic || [https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf Time]
|-
| [[Simplex Algorithm ( Linear Programming)|Simplex Algorithm]] || 1947 || $O({2}^n*poly(n, m))$ || $O(nm)$ || Exact || Deterministic ||  
|-
| [[Terlaky's Criss-cross algorithm ( Linear Programming)|Terlaky's Criss-cross algorithm]] || 1985 || $O({2}^n*poly(n, m))$ || $O(nm)$ || Exact || Deterministic ||  
|-
| [[Affine scaling ( Linear Programming)|Affine scaling]] || 1967 || ? (originally $O(n^{3.5} L)$ but seems unclear) || $O(nm+m^{2})$? || Exact || Deterministic ||  
|-
| [[Cohen; Lee and Song ( Linear Programming)|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 || [https://arxiv.org/abs/1810.07896 Time]
|-
| [[Lee and Sidford ( Linear Programming)|Lee and Sidford]] || 2015 || $O((nnz(A) + n^{2}) n^{0.5})$ || $O(nm+n^{2})$?? || Exact || Deterministic || [https://arxiv.org/abs/1503.01752 Time]
|-
| [[Vaidya ( Linear Programming)|Vaidya]] || 1987 || $O(((m+n)$n^{2}+(m+n)^{1.5}*n)L^{2} logL loglogL) || $O((nm+n^{2})$L)? || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF01580859 Time]
|-
| [[Vaidya ( Linear Programming)|Vaidya]] || 1989 || $O((m+n)$^{1.5}*n*L^{2} logL loglogL) || $O((nm+n^{2})$L)? || Exact || Deterministic || [https://ieeexplore.ieee.org/document/63499 Time]
|-
| [[Jiang, Song, Weinstein and Zhang ( Linear Programming)|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 || [https://arxiv.org/abs/1810.07896 Time]
|-
|}