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

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} logL loglogL)$	$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))$? (previously $O({2}^n)$)	$O(nm)$	Exact	Deterministic
Terlaky's Criss-cross algorithm	1985	$O({2}^n*poly(n, m))$? (previously $O({2}^n)$)	$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