Linear Programming Flashcards
How do you turn a max LP problem into a Min one(or vice versa?)
Just multiply the coefficients of the objective function by -1
How?
How to change an equality constraint into inequalities?
How to deal with a variable x that is unrestriced in sign?
How can a generic LP be expressed using matrices?
Describe the max flow problem in terms of a graph.
define its properties
What its relation to LP - what constraints we have?
- What does the simplex algorithm do?*
- where does it start and what it does with each iteration?*
- define the path from s to t, define its edges, how can each kind of edge increase the stream?*
It starts with zero flow.
With each iteration it tries to find a shortest path from s to t. then, it tries to maximize the stream.
This path is constisted of two kinds of edges (u,v):
(u,v) is in the original network and is not yet in max capacity
the reverse (v,u) is in the original netwrok, and there is some flow along it.
In the first case: f can be increased no more than c(u,v)-f(u,v)
In the second case: f can be increased up to f(v,u) additional units
Define an (s,t)-cut
prove
How can you turn a bipartite matching into a max flow program and then to a LP one?
Write in matrix form the dual LP
Write the Duality theorem
NOTE: in the dual, if we have equality in the primal, the y’s in the dual aren’t restricted to be non-negative.
Which property regarding to zero games is suprising?
Explain
How should Row choose its strategy if he nows Colums will choose the best pure solution he can?
For fixed x1 and x2, write the LP of the attached image
then how can Row maximize the minimal value of Column
Write the Max of Column if he chooses first the strategy
- The Simplex algorithm:*
- Any setting of the xi’s can be represented by an _____ of real numbers and plotted in n-dimensional space*
A linear equation involving the xi’s defines a _______ it this same space R^n
A linear inequality involving the xi’s defines a _______ it this same space R^n
what is an half-space?
The feasible region of the linear program is specified by… ?
- The Simplex algorithm:*
- Any setting of the xi’s can be represented by an n-tuple of real numbers and plotted in n-dimensional space.*
A linear equation involving the xi’s defines a hyperplane it this same space R^n
A linear inequalityinvolving the xi’s defines ahalf-space it this same space R^n
Half space defines all points that are either precisely on the hyperplane or lie on one particular side of it.
the feasible region of the linear program is specifed by a set of inequalities and is therefore the intersection of the corresponding half-spaces, a convex polyhedron.
define a vertex in terms of hyperplanes
Each vertex is the unique point at which some subset of hyperplanes meet.
Each vertex is specified by a set of _ equalities.
Describe the notion of a neighbour.
If we’re in the origin, how do we operate in the simplex algorithm?
How do we proceed if vertex u is not at the origin?
we look at the inequalities which define u.
we make the equation to be of the form:
expression >= 0.
then assign - yi = expressioni.
Then we change the subject function accordingly.
If all coefficients are negative - we’re done!
Prove:
x is a vertex -> for all w!=0 in R^n, x+w or x-w is not in the polyhedron
clue: prove that there exists j such that Aj*w != 0
Assume x is in the polyhedron and it satisfies that for all w!=, w+x or w-x is not in the polyhedron. Prove that x is a vertex.
Write the LP of the following problem
Prove that the vertices of the polyhedron are integrals, and therefore the solution for the LP is an integral vector.
Step 1:
prove that since 0<xij></xij>
<p>step2:</p>
<p>How did we create Xodd and Xeven and why (Xodd+Xeven)/2 = X?</p>
<p>step 3:</p>
<p>Why (Xodd+Xeven)/2 = X means that X is not a vertex?</p>
</xij>
Write the Dual for the Min-cut-Max Flow problem.
What can we conclude from the condition?
We can conclude that we must remove at least one edge from any path from s to t. That is, we create the minimal cut.
Which lemma is used in order to prove that?
Prove that Min-Cut > = Dual
Prove that MinCut >= Dual
what are the steps?
- Think of Ye as the weight on the edges
- d(u) is the shortest path from s to u
- Run dijkstra to find these values
- For arbitrary 0
- For every P, S is a cut.
- The expected value on the weights of all cuts <= the value of the Dual.
- Therefore there must exists atleast one cut S for which S<= the value of the Dual.
Prove that the expected value on the weights of all cuts <= the value of the Dual
For every e = (u,v) in E define the random variable Xe such that:
Xe = 1 if u in S, v not in S
Xe = 0 else
What is the expected value of E[Xe]?
E[Xe] = Pr[Xe = 1] <= d(v) - d(u) <= Ye
Why?
Pr[Xe = 1] -> d(u) <= p < d(v) ->. What is the chance to choose p that is between d(u) and d(v)? exactly p.
Ye is the length of the edge e=(u,v), and we know that
d(v) <= d(u) + w(u,v) = d(u) + Ye
Define the Multiway-Cut problem
- Undirected graph G = (V,E)
- Each edge has a non negative value
- We are given S1,..,Sk in V
- Looking for a subset F of E such that in the graph
* (V, E\F) there is no path there is no path from Si to Sj for all 1<=i<j>minimize C(F)</j>
- Looking for a subset F of E such that in the graph
- For k=2 it’s exactly a min-cut
- For k>2 it is NP-hard.
Assume we have a solution F for the Multiway Cut problem, for some k. What the graph (V, E\F) looks like?
It has at least k connected components,
where for each Si, Sj, they are surely not in the same connected component.
That is, if Si is in Ci, and Sj is in Cj, it is certain that Ci != Cj.
Write the algorithm for the Multiway-Cut approximation:
The algorithm returns a set F of edges such that C(F)<=2C(F*)
Where F* is the optimal cut.
For every i we find a minimal cut that seperates Si from all the rest.
Eventually we return the union of all these edges subsets.
Why for the approximation algorith, for the edge set F,
C(F) <= 2C(F*), where F* is the optimal cut.
- 1. Recall that for every Si, Ci denotes its connected component.
- 2. Let Fi* denote the set of edges e =(u,v) s.t. either u or v belong to Ci*. That is, the connected component of i for the optimal solution.
- 3. Since F* is an optimal solution, Fi* separates Si from all others, and C(Fi) <= C(Fi*), since Fi the Opt for k=2.
-
4. Now, since every edge e = (u,v) in F* appears both for i and both for j, we know that the sum of the weights on all k connected components is smaller than 2C(F*).
*
Write the linear program for the multiway-cut problem.
Note the subjective is not valid for an LP, how can we turn it into one?
write the first rounding attempt algorithm of MW LP
Analyze the first rounding attempt.
For the edge (u,v) what is the chance of u and v to be seperated by the algorithm?
- The algorithm creates a feasible soultion.
- The expected value is smaller than 2OPT_LP
We check over the terminals arbitrarily, what is the probability that terminal j is the first to seperate u,v?
Prove
How can we get a 3/2 approximation?
The 0..0 might not be a vertex, what should we do?
After we found a vertex to begin with, what shall we do?
Assume it is (2,0)
How can we recognize an unbounded LP?
