SA
메인 내용으로 이동

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.

OPT[v,k]=min(OPT[v,k1],OPT[u,v]+w(u,v))\text{OPT}[v,k] = \min(\text{OPT}[v, k-1], \text{OPT}[u, v] + w(u,v))

Chain Matrix Multiplication

OPT[i,j]=OPT[i,k]+OPT[k+1,j]+combine\text{OPT}[i, j] = \text{OPT}[i, k] + \text{OPT}[k+1, j] + \text{combine}

Min Cut

The set of vertices reachable from source s in the residual graph is one part of the partition. Cut capacity cap(A,B)=out Ac(e)\text{cap}(A, B) = \sum_{\text{out A}} c(e).

f=e out of Xf(e)e into Xf(e)|f| = \sum_{e~\text{out of X}} f(e) - \sum_{e~\text{into X}} f(e)
  • maxflow = Min cap(A,B)\text{cap}(A, B).

Ford-Fulkerson

Given (G,s,t,cN+)(G, s, t, c \in \mathbb{N}+), start with f(u,v)=0f(u,v)=0 and Gf=GG_f =G. While an augmenting path is in GfG_f, find a bottleneck. Augment the flow along this path and update the residual graph GfG_f. O(f(V+E))\mathcal{O}(|f| (V+E)).

Edmond-Karp

Ford-Fulkerson, but choose the shortest augmenting path.

For any flow ff and any (A,B)(A,B) cut, fcap(A,B)|f| ≤ \text{cap}(A,B). For any flow ff and any (A,B)(A,B) cut, f=f(s,v)=uA, vBf(u,v)uA, vBf(v,u)|f| = \sum_f (s, v) = \sum_{u \in A,~v \in B} f(u, v) - \sum_{u \in A,~v \in B} f(v, u)

Solving by Reduction

To reduce a problem YY to a problem XX (YpXY \leq_{p} X) we want a function ff that maps YY to XX such that ff is a polynomial time computable and yY\forall y \in Y is solvable if and only if f(y)Xf(y) \in X 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.
  • O(f(E+V))\mathcal{O}(|f| (E' + V'))
  • f=V|f| = V
  • V=2V+2V' = 2V + 2
  • E=E+2VE' = E + 2V
  • O(V(E+2V+2V+2))=O(VE+V2)=O(VE)\mathcal{O}(V (E + 2V + 2V + 2)) = \mathcal{O}(V E + V^2) = \mathcal{O}(V E)

Circulation

  • d(v)>0d(v) > 0 if demand
  • d(v)<0d(v) < 0 if supply
  • Capacity Constraint 0f(e)c(e)0 \leq f(e) \leq c(e)
  • Conservation Constraint fin(v)fout(v)=d(v)f^{\text{in}} (v) - f^{\text{out}} (v) = d(v).
  • For every feasible circulation vVd(v)=0\sum_{v \in V} d(v) = 0, there is a feasible circulation with demands d(v)d(v) in GG if and only if the maximum sts-t flow in GG' has value D=d(v)>0d(v)D = \sum_{d(v)>0} d(v).

Circulation with Demands and Lower Bounds.

  • Capacity Constraint l(e)f(e)c(e)l(e) \leq f(e) \leq c(e)
  • Conservation Constraint fin(v)fout(v)=d(v)f^{\text{in}} (v) - f^{\text{out}} (v) = d(v)
  • Given GG with lower bounds, we subtract the lower bound l(e)l(e) from the capacity of each edge.
  • Subtract f0in(v)f0out(v)=L(v)f_0^{\text{in}}(v) − f_0^{\text{out}}(v) = L(v) from the demand of each node.
  • Solve the circulation problem on this new graph to get a flow ff.
  • Add l(e)l(e) to every f(e)f(e) 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 PP.
  • If SS is empty, Linear Programming has no solution.``
  • If SS is unbounded, Linear Programming may or may not have the solution.
  • If SS is bounded, Linear Programming has one or more solutions.

Standard Form Linear Programming

  • max(c1x1++cnxn)\max (c_1x_1 + \cdots + c_nx_n)
  • subject to
  • a11x1++a1nxnb1a_{11}x_1 + \cdots + a_{1n}x_n ≤ b_1
  • all the way to
  • am1x1++amnxnbma_{m1}x_1 + \cdots + a_{mn}x_n ≤ b_m.
  • Also, x10,,xn0x_1 \geq 0, \cdots, x_n \geq 0.

Matrix Form Linear Programming

  • max(cTx)\max(c^T x)
  • subject to
  • AxbAx \leq b
  • x0x \geq 0
  • xRx \in \mathbb{R}

Integer Linear Program

  • all variables N\in \mathbb{N}
  • is NP-Hard

Dual Program

  • min(bTy)\min(b^T y)
  • subject to
  • ATycA^T y \geq c
  • y0y \geq 0
  • yRy \in \mathbb{R}

Weak Duality

  • The optimum of the dual is an upper bound to the optimum of the primal.
  • OPT(primal)OPT(dual)\text{OPT}(\text{primal}) ≤ \text{OPT}(\text{dual}).

Strong duality

  • Let P and D be primal and dual Linear Programming correspondingly. If P and D are feasible, then cTx=bTyc^T x = b^T y.

If a standard problem and its dual are feasible, both are feasibly bounded. If one problem has an unbounded solution, then the dual of that problem is infeasible.

Possibilities of Feasibility

P\DFeasibly BoundedFeasibly UnboundedInfeasible
Feasibly BoundedPossibleImpossibleImpossible
Feasibly UnboundedImpossibleImpossiblePossible
InfeasibleImpossiblePossiblePossible

P vs. NP

  • P = set of poly-time solvable problems.
  • NP = set of poly-time verifiable problems.
  • Decision Knapsack is NP-complete, whereas undecidable problems like Halting problems are only NP-Hard (not NP).
  • X is NP-Hard if YNP\forall Y \in NP and YpXY \leq_p X.
  • X is NP-complete if X is NP-Hard and XNPX \in NP.
  • If P = NP, then P = NP-complete.
  • NP Problems can be solved in poly-time with NDTM.
  • NP Problems can be verified in poly-time by DTM.

Polynomial Reduction

To reduce a decision problem Y to a decision problem X (YpXY \leq_p X), find a function ff that maps Y to X such that ff is poly-time computable and yY\forall y \in Y is YES if and only if f(y)Xf(y) \in X is YES.

Proving NP-Complete

Show X is in NP, Pick problem NP-complete Y, and show YpXY \leq_p X.

Conjunctive Normal Form SAT

  • Conjunction of clauses.
  • Literal: Variable or its negation.
  • Clause: Disjunction of literals.
  • 3-SAT. Each clause has at most three literals.
  • (X1¬X3)(X1X2X4)(X_1 \lor \neg X_3) \land (X_1 \lor X_2 \lor X_4) \land \cdots

Independent Set

  • Independent Set is a set of vertices in a graph, no two of which are adjacent.
  • The max independent set asks for the size of the largest independent set in a given graph.

Clique

  • Complete graph = every pair of vertices is connected by an edge.
  • The max clique asks for the number of vertices in its largest complete subgraph.

Vertex Cover

  • Vertex Cover of a graph is a set of vertices that includes at least one endpoint of every edge.
  • The min vertex cover asks for the size of the smallest vertex cover in a graph.

Hamiltonian Cycle

  • A cycle that visits each vertex exactly once.
  • Hamiltonian Path visits each vertex exactly once and doesn't need to return to its starting point.

Graph Coloring

  • Given G, can you color the nodes with <k<k colors such that the end points of every edge are colored differently?

이 문서를 언급한 문서들