In the real world, it is usually cheaper when you buy some thing in a bulk because of the delivery costs. Now think about a undirected graph $G$ $=$ $(V,E)$ with length $l_e$ $\ge$ $0$ for all $e$ $\in$ $E$. This problem requires $k$ pairs of vertices $(s_i,t_i)$ and demand $d_i$. One thing that makes this problem interesting is that there is a cost function $f(u)$ such that satisfies following.

For a given vertices $V$ and distance $V \times V \rightarrow \mathcal{R} : d$. $(V,d)$ is so called a metric if following properties are hold.

1. $\ln n$ $\le$ $\sum\limits_{k = 1}^{n} \frac{1}{k}$ $\le$ $\ln n$ $+$ $1$ for $n$ $\in$ $\mathbb{Z}^{+}$
2. $\sum\limits_{k = 1}^{n}ar^{k-1}$ $=$ $a\frac{r^{n} - 1}{r - 1}$ if $r$ $\neq$ $1$, $n$ $\in$ $\mathbb{Z}$

We need some definitions and theorems to discuss about the coloring.

If $X$ is a nonnegative random variable and $a \gt 0$ then, $Pr[X \ge a]$ $\le$ $\frac{E(X)}{a}$.

To show what is semidefinite programming, we need to know what is semidefinite matrix. Notice that $x$ $=$ $\mathcal{R}^{n}$ $=$ $\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}$.

Now, we will re visit the uncapacitated facility location problem. Before we proceed new methodology for the uncapacitated facility location problem, we can extend some terminology for assignment costs between clients or facilities either. For example, assignment costs between client $i$ and $j$ can be the shortest path between client $i$ and $j$. If we define this as so, it is known to reserve the solution because of the metric closure.

There is a problem known as a steiner tree problem. The steiner tree problem is a problem to find a minimum edge set that connects every vertex in $S \subseteq V$ from a given graph $G = (V,E)$. Notice that this problem doesn’t care whether you included some vertices $v \in V - S$ in the edge set. Moreover, this problem is a superset of the minimum spanning tree problem and shortest path problem. We can construct problem like $S = V$ or $S = \{s, t\}$ to solve the minimum spanning tree problem and shortest path problem repectively. Notice that this problem will result in a tree because it will not have a cycle which doesn’t make sense for minimum edge set with connectivity.

The uncapacitated facility location problem is a problem to decide which facility to open and how to handle clients for it. Notice that every client will just go to the closest facility because there is no capacity limits.

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