Discrete Mathematics
Dynamic Programming
- Optimal substructure. The optimal solution to a problem consists of optimal solutions to subproblems.
- Overlapping subproblems. few subproblems in total, many recurring instances of each.
Bellman-Ford
shortest path, negative possible.
Chain Matrix Multiplication
Min Cut
The set of vertices reachable from source s in the residual graph is one part of the partition. Cut capacity .
- maxflow = Min .
Ford-Fulkerson
Given , start with and . While an augmenting path is in , find a bottleneck. Augment the flow along this path and update the residual graph . .
Edmond-Karp
Ford-Fulkerson, but choose the shortest augmenting path.
For any flow and any cut, . For any flow and any cut,
Solving by Reduction
To reduce a problem to a problem () we want a function that maps to such that is a polynomial time computable and is solvable if and only if is solvable.
Reduction to NF
Describe how to construct a flow network. Claim "This is feasible if and only if the max flow is …". Prove both directions.
Bipartite to Max Flow
- Max Matching ⟹ Max Flow. If k edges are matched, then there is a flow of value k.
- Max matching ⟸ Max flow. If there is a flow f of value k, there is a matching with k edges.
Circulation
- if demand
- if supply
- Capacity Constraint
- Conservation Constraint .
- For every feasible circulation , there is a feasible circulation with demands in if and only if the maximum flow in has value .
Circulation with Demands and Lower Bounds.
- Capacity Constraint
- Conservation Constraint
- Given with lower bounds, we subtract the lower bound from the capacity of each edge.
- Subtract from the demand of each node.
- Solve the circulation problem on this new graph to get a flow .
- Add to every to get a flow for the original graph.
Existence of Linear Programming Solution.
- Given an Linear Programming problem with a feasible set and an objective function .
- If is empty, Linear Programming has no solution.``
- If is unbounded, Linear Programming may or may not have the solution.
- If is bounded, Linear Programming has one or more solutions.
Standard Form Linear Programming
- subject to
- all the way to
- .
- Also, .