Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithms 2 > Linear Programming > Flashcards

Linear Programming Flashcards

1
Q

How do you turn a max LP problem into a Min one(or vice versa?)

A

Just multiply the coefficients of the objective function by -1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How to change an equality constraint into inequalities?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How to deal with a variable x that is unrestriced in sign?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How can a generic LP be expressed using matrices?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Describe the max flow problem in terms of a graph.

define its properties

What its relation to LP - what constraints we have?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q
  • 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?*
A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Define an (s,t)-cut

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

prove

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How can you turn a bipartite matching into a max flow program and then to a LP one?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Write in matrix form the dual LP

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Write the Duality theorem

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

NOTE: in the dual, if we have equality in the primal, the y’s in the dual aren’t restricted to be non-negative.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Which property regarding to zero games is suprising?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Explain

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How should Row choose its strategy if he nows Colums will choose the best pure solution he can?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

For fixed x1 and x2, write the LP of the attached image

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

then how can Row maximize the minimal value of Column

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Write the Max of Column if he chooses first the strategy

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q
  • 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… ?

A
  • 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.

21
Q

define a vertex in terms of hyperplanes

A

Each vertex is the unique point at which some subset of hyperplanes meet.

22
Q

Each vertex is specified by a set of _ equalities.

Describe the notion of a neighbour.

A
23
Q

If we’re in the origin, how do we operate in the simplex algorithm?

A
24
Q

How do we proceed if vertex u is not at the origin?

A

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!

25
Q

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

A
26
Q

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.

A
27
Q

Write the LP of the following problem

A
28
Q

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>

A
29
Q

Write the Dual for the Min-cut-Max Flow problem.

What can we conclude from the condition?

A

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.

30
Q

Which lemma is used in order to prove that?

A
31
Q

Prove that Min-Cut > = Dual

A
32
Q

Prove that MinCut >= Dual

what are the steps?

A
  • 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.
33
Q

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]?

A

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

34
Q

Define the Multiway-Cut problem

A
    1. Undirected graph G = (V,E)
    1. Each edge has a non negative value
    1. We are given S1,..,Sk in V
    1. 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>
    1. For k=2 it’s exactly a min-cut
    1. For k>2 it is NP-hard.
35
Q

Assume we have a solution F for the Multiway Cut problem, for some k. What the graph (V, E\F) looks like?

A

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.

36
Q

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.

A

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.

37
Q

Why for the approximation algorith, for the edge set F,

C(F) <= 2C(F*), where F* is the optimal cut.

A
  • 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*).
    *
38
Q

Write the linear program for the multiway-cut problem.

A
39
Q

Note the subjective is not valid for an LP, how can we turn it into one?

A
40
Q
A
41
Q

write the first rounding attempt algorithm of MW LP

A
42
Q

Analyze the first rounding attempt.

For the edge (u,v) what is the chance of u and v to be seperated by the algorithm?

A
  1. The algorithm creates a feasible soultion.
  2. The expected value is smaller than 2OPT_LP
43
Q

We check over the terminals arbitrarily, what is the probability that terminal j is the first to seperate u,v?

A
44
Q

Prove

A
45
Q

How can we get a 3/2 approximation?

A
46
Q
A
47
Q

The 0..0 might not be a vertex, what should we do?

A
48
Q

After we found a vertex to begin with, what shall we do?

Assume it is (2,0)

A
49
Q

How can we recognize an unbounded LP?

A

Algorithms 2 (9 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions