Survivable network design is a problem that designing a network that can survive from disconnecting some edges.

Integer multicommodity flow problem is a problem to avoiding congetstion in edges. It can be used at the field of circuit design because avoiding critical path is a typical problem in a circuit design. Now, let’s fomulating a problem.

Let $X_1, X_2, \cdots, X_n$ be $n$ independent varaible which are between $0$ and $1$. Then,
$Pr[X \ge (1 + \delta)U] \lt (\frac{e^{\delta}}{(1 + \delta)^{1 + \delta}})^U$,
$Pr[X \le (1 - \delta)L] \lt (\frac{e^{-\delta}}{(1 - \delta)^{1 - \delta}})^L$.
For $X = \sum\limits_{i=1}^n X_i$, $\mu = E[X]$, $L \le \mu \le U$ and $\delta > 0$.

A graph is a typical data structure which is used to represent some relations between nodes. From any graph, we can imagine a flow of a graph $G$. Formally, flow of the graph is defined like follow. For a given graph $G= (V, E)$, flow $f$ is a mapping function $V \times V \rightarrow \mathcal{R}$. To be a flow, there are some requirements. If there is a capacity $c$ for edeges $c : V \times V \rightarrow \mathcal{R}$, which $(u,v) \in E$ iff $c(u,v)$ exists. Then flow of graph can’t exceed that capacity. Which means $f(u,v) \le c(u, v)$. Also it requires two variables which are source $s$ and destination $t$. Then $\sum\limits_{(i, v) \in E, v \neq s,t}f(i, v) = \sum\limits_{(v, j) \in E, v \neq s,t}f(v, j)$. Which means that every value goes in $v$ should go out from $v$ either. Then we can evaluate this flow $f$ as $\sum\limits_{(s, v) \in E}f(s, v) - \sum\limits_{(v, s) \in E}f(v, s)$ $=$ $\sum\limits_{(v, t) \in E}f(v, t) - \sum\limits_{(t, v) \in E}f(t, v)$.

Unweighted version

Minimizing the sum of completion time is a typical scheduling problem. Let’s think that there are $n$ works to be done. With these works, let $r_1, r_2, \cdots, r_n$ as release dates and $p_1, p_2, \cdots, p_n$ as processing times. Now we will schedule that $n$ works in some order. With that order, let’s define $C_1, C_2, \cdots, C_n$ as times that each work finished. The problem is to find a schedule that minimize $\sum\limits_{i=1}^n C_i$. Notice that this machine is a nonpreemptively which means each work can’t interrupt other works.

Linear programming is constructed with two factors.

1. Objective function which is a mizimizing/maximizing target.
2. Constraints Which are requirements for the problem.

Minimum-degree spanning tree problem is a problem to minimize the degree of the spanning tree from given graph. Formally, problem is like below. Given a graph $G = (V,E)$, minimized the $\max_{v \in V} deg(v)$ from a spanning tree $T$ of $G$. Notice that this is a NP-hard problem.

Page rank

Page rank is an algorithm to determine which vertices are important and which aren’t. For each iteration, each vertex will be updated by nearby vertices. Let’s define some terms.

1. $r_i^t$ as the value of vertex $i$ at the $t$th iteration such that $\sum\limits_{i \in V}r_i^0 = 1$.
2. $\delta(i)$ as the set of neighbor vetices of vertex $i$.
3. $\beta$ is a convergance ratio which means $0 \le \beta \le 1$.

MPI is a programming model for parallel programming. It transfers data between any processing unit without detailed set-up. For example, let’s assume there are 4 machines with 16 core CPU. Then, it will have 64 cores in total. Then, MPI uses 64 cores with out any consideration but just equally.

There are some algorithm families.