Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2014:journals:eric:home [2014/03/25 20:03] – [Eric's Journal] utomoe | courses:cs211:winter2014:journals:eric:home [2014/03/31 14:36] (current) – [Eric's Journal] utomoe | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Eric's Journal ====== | ====== Eric's Journal ====== | ||
| + | Interest: 7/10. this is back to bit too abstract for me. maybe (in fact probably) this week's reading will help out if I take big data class this fall. it seems network flow would be huge part of big data since it's about partitioning too big a set to compute with x resources into smaller sets with x*y resources | ||
| + | ===== Week 11 Reading ===== | ||
| + | ====7.1 The Max-Flow Prob and the Ford-Fulkerson Alg==== | ||
| + | >the prob: graphs through nodes and switches act as transportation networks with traffic of certain capacities traveling through, and having source nodes and sink nodes for that data | ||
| + | -flow networks | ||
| + | * flow: abstract entity gen by source nodes | ||
| + | * flow network: directed graph with following features: | ||
| + | * capacity, a nonnegative number ce | ||
| + | * source node s in V | ||
| + | * sink node t in V | ||
| + | * internal nodes in between | ||
| + | -defining flow: 0< | ||
| + | -the max-flow prob: arrange traffic in a flow network as efficiently as poss (max the flow value) | ||
| + | * by cutting a graph, we can know the max possible flow value | ||
| + | * minimum cut: max-flow value equals the minimum capacity of any such division | ||
| + | > | ||
| + | -the residual graph: node set of Gf is same as G, ce-f(e) leftover units of capacity on edges to push forward to, and backward edges e' | ||
| + | -aug paths in a res graph | ||
| + | aug(f,P) | ||
| + | let b=bottleneck(P, | ||
| + | for each edge in P | ||
| + | if edge is forward: increase f(e) in G by b | ||
| + | else: decrease f(e) in G by b | ||
| + | * 7.1 f' is a flow in G | ||
| + | * proof: 0< | ||
| + | Max-Flow | ||
| + | all e in G to 0 | ||
| + | while there' | ||
| + | let P be that simple plath | ||
| + | f' | ||
| + | update f to be f' | ||
| + | update Gf to be Gf' | ||
| + | | ||
| + | * the above is the FF alg who dev in 1956 | ||
| + | >ana the alg: termination and RT | ||
| + | -7.2: at every intermediate stage of FFA, flow values{fe} and the resi caps in Gf are ints. Proof: suppose true after the while loop j iterations, then bn(P,f) will be an it and f' will have ints so will the new res graph | ||
| + | -7.3: let f be a flow in G, and P a simple st path in G. Then vf' | ||
| + | -7.4: suppose as above that all caps in G are ints. Then the FFA terminates i nat most c iterations of the while loop. Proof: by 7.3 flow in FFA increases each iter, and by 7.2 at least by 1. it starts with 0 and not higher than c, so that's max c iters | ||
| + | -7.5 suppose that all caps in G are ints, then FFA can be implemented to run in mC time. Proof: most work done in one iter is f. have two linked lists for each node in Gf, then to find path st we can use breadfirst or depthfirst in )(m+n). then for each e we can construct forward and backward edges in Gf' in Om time | ||
| + | ====7.2 max flows and min cuts in a network==== | ||
| + | >ana the alg: flows and cuts: structure is important because the max flow is determined by any point where it's just one point connecting two separate cut sets | ||
| + | -7.6: let f be any st flow and AB and set cut. then vf=fout(A) - fin(A). Proof: vf = foutv-finv for all v in A. Then that equals feoutA - feinA = foutA-finA | ||
| + | -7.7 let f be any st flow and AB any st cut then vf=finB-foutB | ||
| + | -7.8: vf< | ||
| + | >ana the alg: max-flow equals min-cut | ||
| + | -7.9: if f is an st flow such that there is no st in Gf, then there' | ||
| + | -7.10:the flow f_ ret by FFA is a max flow | ||
| + | -7.11: given f of max val we can compute st of min cap in m time. proof: 79 then bfs or dfs to find A*, then B*=v-A* and return cut(A*,B*) | ||
| + | -7.12: in every flow network there f and cut so that vf=c(A,B) | ||
| + | -7.13: in every flow network the max val of st flow is equal to min cap of st cut | ||
| + | -further analysis: integer valued flows | ||
| + | --7.14: if all caps in flow network are ints then there is max flow f for which every flow val fe is an its | ||
| + | --real #s as caps? all the theorems here were assumed that caps had to be ints. but what if they' | ||
| + | |||
| + | ====7.3 choosing good aug paths==== | ||
| + | >the upper bound can be very bad if each bottleneck is the same in graph as in res graph, and if that bottleneck were potentially one. then to get flow value of 200, for example, we'd have to do 200 augmentations | ||
| + | >Des a faster flow alg | ||
| + | Scaling Max-Flow | ||
| + | set all e in G to 0 | ||
| + | set D to be largest power of 2 no larger than max cap out of s | ||
| + | while D>=1 | ||
| + | while there' | ||
| + | let P be a simple st path in GfD | ||
| + | | ||
| + | | ||
| + | D = D/2 | ||
| + | | ||
| + | >ana the alg | ||
| + | -7.15: if the caps are int vals then throughout the SMFA the flow and res caps are ints, implying when D=1, GfD is same as Gf and hence when the alg terminates the flow, f is of max value | ||
| + | -7.16: the number of iters of the outer while loop is at most 1+logC | ||
| + | -7.17: during the Dscaling phase, each aug increases the flow val by at least D | ||
| + | -7.18 let f be the flow at the end of the Dscaling phase. There is st cut AB in G for which CAB< | ||
| + | -7.19 the # of augs in scaling phase at most 2m | ||
| + | -7.20 the SMFA in graph with m edges and its is at most 2m(1+logc) augs and runs in at most m^2logc time | ||
| + | > | ||
| + | |||
| + | ====7.5 a first app: the bipartite matching problem==== | ||
| + | >the prob: bipartite graph unidirected whose node set can be partitioned. a matching is a subset M such that each node apppears in at most one edge in M | ||
| + | >des the alg: direct all X to Y, then add node s and sx to each X then to and Y to t, then each edge a cap of 1 | ||
| + | >ana the alg | ||
| + | -7.34: M' contains k edges cuz in the cut set, first is cardinality of M' while second is 0 since nothing enters A, so M' contains k edges | ||
| + | -7.35: each X is the tail of at most one edge in M': if tail of 2, 2 units of flow leave from x, so 2 must have come into X but the cap is 1 so that can't be | ||
| + | -7.36: each Y is the head of at most one edge in M' | ||
| + | -7.37: the size of max match in G is equal to val of max flow in G' and the edges in such a matching G are the edges that carry flow from X to Y in G' | ||
| + | -bounding the running time | ||
| + | * 7.38: the FFA can be used to find a max matching in a bip graph in O(mn) time | ||
| + | * better bounds from 7.3 would not give better RT oddly enough because these bounds were for all instances of C where as before C had to be small enough | ||
| + | * aug paths are also called alternating paths in the context of finding max matching | ||
| + | -Extensions: | ||
| + | -what if the graph doesn' | ||
| + | -7.40: assume bip G with XY has |X|=|Y|. then G has either perfmat or there' | ||
| + | -proof 7.40: show val of maxflow in G' is n; by mfmct we know A' contains s from XY. assume by 7.11 A' | ||
| + | |||
| + | ====7.7 extensions to the max flow prob==== | ||
| + | >the prob: circulations with demands: consider fixed supply and fixed demand values and shift flow to meet those demands (like highway or railway of shipping routes). So now G has dv>0 and supply of -dv. set S to ann nodes with negative demand T to nodes with pos demands | ||
| + | 1) cap conditions: for each e in E we have 0< | ||
| + | 2) demand conditions: for each v we have v finv-foutv = dv | ||
| + | -feasibility prob: does circulation meeting 1 and 2 exist? | ||
| + | -7.49: if there exists feas circ with demands dv then sum of vs in dv = 0 | ||
| + | -proof of 7.49: dv must = finv - foutv so e is counted twice and cancel out. so dv = 0 | ||
| + | >des and ana an alg for circs: attach super source s* and super sink t* to each node in T, then add those to G. for each v in T add edge vt* with cap dv and each u in S add s*u with capacity -du then carry over rest of G to G' | ||
| + | -7.50: there' | ||
| + | -7.51: the graph G has fc with dv iff for all cuts AB, dv< | ||
| + | >the prob: circs with demands and lower bounds | ||
| + | -lower bounds are used to force/ | ||
| + | 1) cap conditions: each e in E, le< | ||
| + | 2) dem cond: each v in V finv-foutv = dv | ||
| + | >des and ana an alg with lower bounds | ||
| + | -consider f0inv - f0outv = leeinv - leeoutv then we have ce-le units to work with in remainder, so in G' the capacities of the edges will be ce-le and demand of node v dv-Lv | ||
| + | -7.52: there' | ||
| + | -proof of 7.52: finv-foutv = einv(le+f' | ||
| + | and conversely f'inv - f'outv = (fe-le)einv - (fe-le)eoutv = dv-Lv so G' stipulations are met | ||
| Interest: 8/10. partly because now we're dealing with non-binary, but multifaceted problems, and largely because it's week11! semester almost over. but not quite. | Interest: 8/10. partly because now we're dealing with non-binary, but multifaceted problems, and largely because it's week11! semester almost over. but not quite. | ||
| ====CHAPTER 6: DYNAMIC PROGRAMMING==== | ====CHAPTER 6: DYNAMIC PROGRAMMING==== | ||
| - | ===6.1 weighted int scheduling: a rec procedure=== | + | ====6.1 weighted int scheduling: a rec procedure==== |
| -des a rec alg | -des a rec alg | ||
| * greedy algs can't do anything if the values of the things aren't all 1 | * greedy algs can't do anything if the values of the things aren't all 1 | ||
| Line 34: | Line 146: | ||
| * 6.5: given M of opt values for subprobs findSol returns opt sol in On | * 6.5: given M of opt values for subprobs findSol returns opt sol in On | ||
| - | ===6.2 principles of dynamic prog: memoization or iteration over subprobs=== | + | ====6.2 principles of dynamic prog: memoization or iteration over subprobs==== |
| -des the alg | -des the alg | ||
| IterativeCompOpt | IterativeCompOpt | ||
| Line 46: | Line 158: | ||
| There' | There' | ||
| - | ===6.3 segmented least squares: multiway choices=== | + | ====6.3 segmented least squares: multiway choices==== |
| -we're no longer in binary mode (ooh wow) | -we're no longer in binary mode (ooh wow) | ||
| -the problem | -the problem | ||
| Line 74: | Line 186: | ||
| -analyzing the alg: it's n2 because there is a pair to check for n entries. and then to find ei,j is also linear so its n3, but we can work it down to n2 by using the ingredients of calc for ei,j-1 to find ei,j in constant time. so RT: n^2 | -analyzing the alg: it's n2 because there is a pair to check for n entries. and then to find ei,j is also linear so its n3, but we can work it down to n2 by using the ingredients of calc for ei,j-1 to find ei,j in constant time. so RT: n^2 | ||
| - | ===6.4: subset sums and knapsacks: adding a variable=== | + | ====6.4: subset sums and knapsacks: adding a variable==== |
| -the problem | -the problem | ||
| * we have a single machine with requests, and only a certain time period to them in. so now we have a cut off time and need to decide which jobs to do and which to ignore. | * we have a single machine with requests, and only a certain time period to them in. so now we have a cut off time and need to decide which jobs to do and which to ignore. | ||
