For any given LP, we can construct LP like one of the format follow.

Survivable network design is the problem of building a network that remains connected even after some edges are removed.

The integer multicommodity flow problem aims to minimize edge congestion. It applies naturally to circuit design, where avoiding critical paths is a key concern. We begin by formulating the problem.

Let $X_1, X_2, \ldots, X_n$ be $n$ independent random variables taking values in $[0, 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 data structure that represents relationships between nodes. From any graph, we can define a flow. Formally, the flow of a graph is defined as follows. 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 times is a classic scheduling problem. Suppose there are $n$ jobs to be scheduled. Let $r_1, r_2, \ldots, r_n$ be their release dates and $p_1, p_2, \ldots, p_n$ be their processing times. We schedule all $n$ jobs in some order. Let $C_1, C_2, \ldots, C_n$ be the completion times of the jobs in that order. The goal is to find a schedule that minimizes $\sum\limits_{i=1}^n C_i$. The machine is non-preemptive, meaning a job cannot be interrupted once started.

A linear program consists of two components.

1. An objective function to minimize or maximize.
2. Constraints that define the feasible region.

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.

PageRank

PageRank is an algorithm that determines the relative importance of vertices in a graph. For each iteration, each vertex will be updated by nearby vertices. Let’s define some terms.

1. $r_i^t$ as the rank of vertex $i$ at iteration $t$, with $\sum\limits_{i \in V}r_i^0 = 1$.
2. $\delta(i)$ as the set of neighboring vertices of vertex $i$.
3. $\beta$ is the convergence damping factor, with $0 \le \beta \le 1$.

MPI is a programming model for parallel and distributed computing. It transfers data between processing units without requiring detailed manual setup. For example, with 4 machines each having 16 CPU cores, there are 64 cores in total. MPI can utilize all 64 cores uniformly without explicit configuration.