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/31 13:51] – [Week 11 Reading] 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: | + | Interest: |
| ===== Week 11 Reading ===== | ===== Week 11 Reading ===== | ||
| ====7.1 The Max-Flow Prob and the Ford-Fulkerson Alg==== | ====7.1 The Max-Flow Prob and the Ford-Fulkerson Alg==== | ||
| Line 55: | Line 55: | ||
| --real #s as caps? all the theorems here were assumed that caps had to be ints. but what if they' | --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==== | ||
