Linear Programming

Question 1

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

Answer 1

Just multiply the coefficients of the objective function by -1

Question 2

How?

Answer 2

Question 3

How to change an equality constraint into inequalities?

Answer 3

Question 4

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

Answer 4

Question 5

How can a generic LP be expressed using matrices?

Answer 5

Question 6

Describe the max flow problem in terms of a graph.

define its properties

What its relation to LP - what constraints we have?

Answer 6

Question 7

• 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?*

Answer 7

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

Question 8

Define an (s,t)-cut

Answer 8

Question 9

prove

Answer 9

Question 10

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

Answer 10

Question 11

Write in matrix form the dual LP

Answer 11

Question 12

Write the Duality theorem

Answer 12

Question 13

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

Answer 13

Question 14

Which property regarding to zero games is suprising?

Answer 14

Question 15

Explain

Question 16

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

Answer 16

Question 17

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

Answer 17

Question 18

then how can Row maximize the minimal value of Column

Answer 18

Question 19

Write the Max of Column if he chooses first the strategy

Answer 19

Question 20

• 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… ?

Answer 20

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

Question 21

define a vertex in terms of hyperplanes

Answer 21

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

Question 22

Each vertex is specified by a set of _ equalities.

Describe the notion of a neighbour.

Answer 22

Question 23

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

Answer 23

Question 24

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

Answer 24

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!

Question 25

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

Answer 25

Question 26

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.

Answer 26

Question 27

*Write the LP of the following problem*

Answer 27

Question 28

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

step2:

How did we create Xodd and Xeven and why (Xodd+Xeven)/2 = X?

step 3:

Why (Xodd+Xeven)/2 = X means that X is not a vertex?

Answer 28

Question 29

Write the Dual for the Min-cut-Max Flow problem. What can we conclude from the condition?

Answer 29

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.

Question 30

Which lemma is used in order to prove that?

Answer 30

Question 31

Prove that Min-Cut **\> =** Dual

Answer 31

Question 32

Prove that MinCut \>= Dual what are the steps?

Answer 32

* 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.

Question 33

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

Answer 33

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

Question 34

# _Define the Multiway-Cut problem_

Answer 34

* 1. Undirected graph G = (V,E) * 2. Each edge has a non negative value * 3. We are given S1,..,Sk in V * 4. 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\<=iminimize C(F) * 5. For k=2 it's exactly a min-cut * 6. For k\>2 it is NP-hard.

Question 35

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

Answer 35

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.

Question 36

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.

Answer 36

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.

Question 37

Why for the approximation algorith, for the edge set F, C(F) \<= 2C(F\*), where F\* is the optimal cut.

Answer 37

* *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\*).* *

Question 38

Write the linear program for the multiway-cut problem.

Answer 38

Question 39

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

Answer 39

Question 40

Answer 40

Question 41

write the first **rounding** attempt algorithm of MW LP

Answer 41

Question 42

Analyze the first rounding attempt. For the edge (u,v) what is the chance of u and v to be seperated by the algorithm?

Answer 42

1. The algorithm creates a feasible soultion. 2. The expected value is smaller than 2OPT\_LP

Question 43

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

Answer 43

Question 44

Prove

Answer 44

Question 45

How can we get a 3/2 approximation?

Answer 45

Question 47

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

Answer 47

Question 48

After we found a vertex to begin with, what shall we do? Assume it is (2,0)

Answer 48

Question 49

How can we recognize an unbounded LP?

Answer 49