MAX-E3SAT is the problem of finding a truth assignment that maximizes the number of satisfied clauses, where each clause contains exactly three literals.

In practice, buying in bulk is typically cheaper due to economies of scale in 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 > 0$, then \(\Pr[X \ge a] \le \frac{E[X]}{a}.\)

To understand semidefinite programming, we first need to define positive semidefinite matrices. Let $x \in \mathbb{R}^{n}$.

We revisit the uncapacitated facility location problem. Before presenting the new approach, we extend the assignment cost notation to include costs between clients as well as between clients and facilities. 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.

The Steiner tree problem asks for a minimum-cost edge set that connects every vertex in a terminal set $S \subseteq V$ in a graph $G = (V, E)$. Steiner trees may include non-terminal Steiner vertices in $V - S$. This problem generalizes both the minimum spanning tree problem (when $S = V$) and the shortest path problem (when $S = {s, t}$). An optimal solution always forms a tree, since any cycle could be removed to reduce cost while preserving connectivity.

The uncapacitated facility location problem asks which facilities to open and how to assign clients to them. Since there are no capacity constraints, every client is assigned to the closest open facility.