Title: Theory / Unimportant / CS / Algo / Approximation / Vazirani +18{ / 2 LP
Tags: récupéré MissingMedia

Name: Linear programming
Definition: problem of optimizing a linear function subject to linear inequality constraints
Page: 94
Chapter: 12
Section: 1
Abbreviation: LP

Name: LP normal form
Definition: find \((x_i)_{j=1}^n\) non-negative
Page: 94
Chapter: 12
Section: 1
Definition2: which minimize \(\sum_{j=1}^nc_jx_j\)
Conjdef: All of
Definition3: such that \((\sum_{j=1}^na_{i,j}x_i\ge b_j)_{i=1}^m\)

Name: A feasible solution
Definition: A value for the \(x_i\)'s which satisfyies the constraints
Page: 94
Chapter: 12
Section: 1
Variables: \(L\) an LP normal form
find \((x_i)_{j=1}^n\) non-negative
which minimize \(\sum_{j=1}^nc_jx_j\)
such that \((\sum_{j=1}^na_{i,j}x_i\ge b_j)_{i=1}^m\)

Definition: A value for the \(x_j\)'s which satisfyies the constraints with \(\sum_{j=1}^nc_jx_j\) minimal
Page: 94
Chapter: 12
Section: 1
Variables: \(L\) an LP normal form
find \((x_i)_{j=1}^n\) non-negative
which minimize \(\sum_{j=1}^nc_jx_j\)
such that \((\sum_{j=1}^na_{i,j}x_i\ge b_j)_{i=1}^m\)
Notation: \(\mathrm z^*\)

Name: The dual problem with \(L\)
Definition: such that \((\sum_{i=1}^ma_{i,j}y_i\le c_j)_{j=1}^m\)
Page: 95
Chapter: 12
Section: 1
Variables: \(L\) an LP normal form
find \((x_i)_{j=1}^n\) non-negative
which minimize \(\sum_{j=1}^nc_jx_j\)
such that \((\sum_{j=1}^na_{i,j}x_i\ge b_j)_{i=1}^m\)
Definition2: which maximize \(\sum_{i=1}^my_jb_i\)
Conjdef: find \((y_j)_{j=1}^m\) non-negative
Typ: Involutive

Smaller0: \(\mathbf y\)
Greater0: \(\sum_{i=1}^mb_iy_i\)
Page: 96
Chapter: 12
Section: 1
Variables: \(L\) an LP normal form
find \((x_i)_{j=1}^n\) non-negative
which minimize \(\sum_{j=1}^nc_jx_j\)
such that \((\sum_{j=1}^na_{i,j}x_i\ge b_j)_{i=1}^m\)
\(D\) its dual program
\(\mathbf y=(y_i)_{i=1}^m\) a vector
Index: 2
Kind: Theo
Smaller to greater: iff
Smaller1: a feasible solution to the dual \(D\)
Name: Weak duality theorem
Greater1: a lower bound on the problem \(L\)
Connect Greater0: is

Smaller0: the optimum to \(L\) is finite
Greater0: the optimum to the dual of \(L\) is finite
Page: 96
Chapter: 12
Section: 1
Variables: \(L\) an LP normal form
find \((x_i)_{j=1}^n\) non-negative
which minimize \(\sum_{j=1}^nc_jx_j\)
such that \((\sum_{j=1}^na_{i,j}x_i\ge b_j)_{i=1}^m\)
Kind: Theo
Smaller to greater: iff
Name: LP-duality theorem
Smallest: the optimum to \(L\) and to its dual are equal

Question: LP programming belong to the complexity class
Answer: NP and co-NP
Page: 96
Chapter: 12
Section: 1

Smaller0: \(\mathbf{x,y}\) are optimal
Greater0: for each \(1\le j\le n\), either \(x_j=0\) or \(\sum_{i=1}^ma_{i,j}y_i=c_j\)
iff
for each \(1\le i\le m\), either \(y_j=0\) or \(\sum_{j=1}^na_{i,j}x_i=b_j\)
Page: 97
Chapter: 12
Section: 1
Variables: \(L\) an LP normal form
find \((x_i)_{j=1}^n\) non-negative
which minimize \(\sum_{j=1}^nc_jx_j\)
such that \((\sum_{j=1}^na_{i,j}x_i\ge b_j)_{i=1}^m\)
\(\mathbf{x,y}\) values for both problems
Assuming: \(\mathbf{x,y}\) are feasible solutions
Name: primal/dual complementary slackness conditions