Problem Set - V                                            11/15/11

(Due at the beginning of class  12/5/11)


CS7800 Advanced Algorithms

This problem set will be graded out of 50 points. It will count for 20% of your final grade.


1)      Linear Programming – different forms

a)      Prove that any linear program can be converted to the standard form: min cTx s.t. Ax = b and x >= 0. [2]

b)      Prove that any linear program can be converted to the canonical form: min cTx s.t. Ax >= b and x >= 0. [2]

c)      State the rules for dualizing an LP in the general form. Show that the dual of the dual is primal. [2]

d)     Give an example for each of the following

·         An LP that is infeasible [1]

·         An LP that is unbounded [1]

e)      Why is the ellipsoid algorithm for solving LPs considered a polynomial-time algorithm but not a strongly polynomial-time algorithm. [2]


2)      LP – some tricks

a)      In class we wrote an LP for max flow. Consider the following generalization of maxflow, called multi-commodity flow: There are k commodities with source si, sink ti and demand di for commodity i. As before the directed graph has capacitated arcs. Write a linear program to compute the maximum fraction f, such that fraction f of each commodity’s demand can be satisfied concurrently. [3]

b)       Consider the nonlinear program (NLP):

       min cTx + dTy (d is nonnegative)

       s.t. Ax + By <= b (all entries of B are nonnegative)

       and y = |x| (i.e. the ith entry of y is the absolute value of the ith entry of x)

i)        First scheme. Prove that the above NLP can be converted to an equivalent LP by adding constraints y >= x and y >= -x. Argue that the NLP and the LP are simultaneously infeasible or feasible with the same objective value. [2]

ii)      Second scheme. Prove that the above NLP can be converted to an LP by creating two new nonnegative vector variables x+ and x_ and setting x = x+ - x_ and y = x+ + x-. Argue that the NLP and the LP are simultaneously infeasible or feasible with the same objective value. [4]

iii)    Prove that if B has negative entries then the problem may have a local minimum that is not a global minimum and hence there can be no equivalent LP formulation. [1]


3)      LP – random stuff from class

a)      Let f(x) denote the square of the distance of the point x from a fixed point B in Rn. Prove that f is a convex function. [3]

b)      Prove that either Ax >= b has a non-negative solution or there is a non-negative y such that yTA <=0 and yTb > 0. [3] (Hint: use Farkas’ Lemma)

c)      Let M be a n x n  matrix with nonnegative entries such that the sum of each column is 1. Prove that there exists a probability vector x (i.e. a vector with nonnegative entries whose sum of entries is 1) such that Mx = x. [4] (Hint: use duality and the fact that if the maximizing dual is feasible and bounded then the primal must be feasible and bounded as well)


4)      LP - applications

a)      Prove that if, at optimality, the value of the dual (primal) variable is non-zero then the corresponding primal (dual) constraint is tight. [2]

b)      von Neumann minmax theorem. Let x and y be probability vectors (i.e. nonnegative vectors whose sum of entries is 1). We will show that

      maxxminy yTAx = minymaxx yTAx. These are bilinear optimization function with     linear constraints and we will show how they can be converted to LPs.     

1.      Give a game-theoretic interpretation of maxxminy yTAx and  minymaxx yTAx. Why is this called a zero-sum game? [2]

2.      Consider maxx miny yTAx. Fix x and consider the LP: {min yT(Ax)| Σ yi = 1, y >= 0}. Now write its dual and add the constraints ∑ xi = 1, x >= 0. Let this be LP-maxmin. Give a game-theoretic interpretation of LP-maxmin. [2]

3.      Write LP-minmax and prove that they are duals of each other. Thus, conclude that maxxminy yTAx = minymaxx yTAx. Show also, that in a zero sum game there is a unique value for all Nash equilibria[3]

4.      Prove that maxx miny yTAx can achieve its optimal value with a y that has exactly one of its entries set to 1 and the rest to 0. [1]


5)      Consider an undirected graph, G = (V, E). Define C(G) = maxS E(S)/|S| as its cohesiveness coefficient, see PS4 Q5 (here S is subset of the vertices, V, and E(S) is the number of edges both of whose endpoints are in S. In PS4 you computed the cohesiveness coefficient using  flow. We will now see how to compute it using LP.

a)      Write an LP to express the cohesiveness coefficient of G. You can write many different LPs but I am looking for a simple one. You only need to use edge variables Puv for (u,v) in E and node variables Qu for u in V, as variables. Q can be a probability vector, i.e. nonnegative entries that sum to 1. Your objective function is simply the maximization of  the sum of the edge variables. You need to figure out what constraints you need. [3]

b)      Let OPT be the optimal value of your LP from 3a. Prove that OPT >= C(G). (Hint: given a maximum cluster S show how to determine a feasible set of values for the node and edge variables that achieves C(G)). [3]

c)      Prove that C(G) >= OPT. Hence conclude that your LP computes C(G). (Hint: There are many ways to prove this. One way is outlined in this hint. The hard part is defining the set S from the values of the edge and node variables at the optimum, i.e. rounding to an integral solution. For r in [0,1] let S(r) be the set of nodes u such that Qu > r.  Show that there exists r such that S(r) achieves the optimum and that you need only consider a polynomial number of r’s). [4]