Description
2 Max Flow, Min Cut, and Duality
In this exercise, we will demonstrate that LP duality can be used to show the max-flow min-cut theorem.
Consider this instance of max flow:
A 7A4
ST S547T
B B
Let f1 be the flow pushed on the path {S,A,T}, f2 be the flow pushed on the path
{S,A,B,T}, and f3 be the flow pushed on max flow in terms of the variables f1, f2, f3:
max f1+f2+f3 f1 + f2≤7 f3≤5 f1≤4 f2≤4 f2 + f3≤7 f1,f2,f3 ≥0
The objective is to maximize the flow being
we can’t push more flow through that edge than its capacity allows.
the path {S,B,T}. The following is an LP for
pushed, with the constraint that for every edge, (a) Find the dual of this linear program, where the variables in the dual are xe for every
edge e in the graph.
(b) Consider any cut in the graph. Show that setting xe = 1 for every edge crossing this cut and xe = 0 for every edge not crossing this cut gives a feasible solution to the dual program.
(c) Based on your answer to the previous part, what problem is being modelled by the dual program? By LP duality, what can you argue about this problem and the max flow problem?
1
(Constraint for (S, A)) (Constraint for (S, B)) (Constraint for (A, T )) (Constraint for (A, B)) (Constraint for (B, T ))
3 How to Gamble With Little Regret
Suppose that you are gambling at a casino. Every day you play at a slot machine, and your goal is to minimize your losses. We model this as the experts problem. Every day you must take the advice of one of n experts (i.e. a slot machine). At the end of each day t, if you take advice from expert i, the advice costs you some cti in [0, 1]. You want to minimize the regret R, defined as:
1T T R = cti(t) − min cti
T t=1 1≤i≤n t=1
where i(t) is the expert you choose on day t. Your strategy will be probabilities where pti denotes the probability with which you choose expert i on day t. Assume an all powerful adversary (i.e. the casino) can look at your strategy ahead of time and decide the costs associated with each expert on each day. Let C denote the set of costs for all experts and all days. Compute maxC(E[R]), or the maximum possible (expected) regret that the adversary can guarantee, for each of the following strategies.
(a) Choose expert 1 at every step, i.e. pt1 = 1 for all t.
(b) Any deterministic strategy, i.e. for each t, there exists some i such that pti = 1.
(c) Always choose an expert according to some fixed probability distribution at every time step. That is, fix some p1,…,pn, and for all t, set pti = pi.
What distribution minimizes the regret of this strategy? In other words, what is argminp1,…,pn maxC(E[R])?
This analysis should conclude that a good strategy for the problem must necessarily be randomized and adaptive.
4 Global Mincut to Min s-t Cut
In class, we showed how to use maximum s-t flow to solve the minimum s-t cut. Now we ask you to consider the global mincut problem. Given a weighted, undirected graph G, the problem asks you to find a minimum weight set of edges whose removal disconnects the graph. (Note that there is no notion of s and t).
Show how to use maxflow or min s-t cut algorithms to solve this problem efficiently. Prove that your reduction would lead to the optimal solution. How many times do you need to invoke the maxflow or min s-t cut subroutine?
5 Dijsktra’s Sort
Show how to use Dijsktra’s algorithm to sort n real numbers (not necessarily non-negative or integral) in ascending order in O(n log n) time. You may use the intermediate outputs of Dijsktra’s to do the sorting (as opposed to using it as a blackbox).
Argue that this means that improving upon the O(m + n log n) run-time of Dijsktra’s algorithm (with Fibonacci heap) would lead to a faster sorting algorithm than merge and quick sort.
Hint: Given the numbers, construct a graph such that the order of vertices being extracted from priority queue by Dijsktra’s algorithm corresponds to the right sorting order.
