We can imagine some clustering problem with $k$-centers. For $G = (V,E)$ with distance $d_{ij} \ge 0$ between each pair of vertices $i,j \in V$. We assume that $d_{ii} = 0, d_{ij} = d_{ji}, d_{ik} + d_{kj} \ge d_{ij}$ for each $i,j,k \in V$. Now, problem is find $S \subset V$ which $|S| = k$. Which makes $max(d(j,S))$ smallest. It’s like making clusters efficiently.

Problem is like below. There is a set of items $I = \{1,2,\cdots,n$}, where each item $i$ has a value $v_i \gt 0$ and a size $s_i \gt 0$. Now, knapsack problem is a “Find the maximum possible value with capacity $B$”.

CUDA is a parallel computing model, architectural API model for GPU. It supports multiple abstractions to handle NVIDIA GPU.

Kronecker product is a mathmatical tools to find all possible combination of something. It can be used for many combinational problem like Traveling-salesman problem.

Matrix representation

There are many formats to represent matrices.

Recap $\operatorname{SET COVER}$ can be LP-relaxed to “Minimize the $\sum\limits_{j=1}^{m} w_j x_j$ such that $\sum\limits_{j:e_i \in S_j} x_j \ge 1$, $x_j \ge 0$ then choose $x_j$ to $1$ which $x_j \ge \frac{1}{f}$ and otherwise to 0”. Which is $f$-approximation algorithm. Which $e_i$ denotes each elements, $S_j$ denotes each subsets, $w_j$ denotes costs of each subsets, $x_j$ is the chocie of each subset. With $f$ is the maximum number of existance of elements.

Recap $\operatorname{SET COVER}$ can be LP-relaxed to “Minimize the $\sum\limits_{j=1}^{m} w_j x_j$ such that $\sum\limits_{j:e_i \in S_j} x_j \ge 1$, $x_j \ge 0$ then choose $x_j$ to $1$ which $x_j \ge \frac{1}{f}$ and otherwise to 0”. Which is $f$-approximation algorithm. Which $e_i$ denotes each elements, $S_j$ denotes each subsets, $w_j$ denotes costs of each subsets, $x_j$ is the chocie of each subset. With $f$ is the maximum number of existance of elements.

An optimization problem is a problem to find minimum/maximum possible soltuion. For example, $\operatorname{SET COVER}$ is a well-known optimization problem. For a universe set $U = \{e_1,e_2,e_3,\cdots,e_n$} and subsets of $U$, $S_j(1 \le j \le n)$. $\operatorname{SET COVER}$ is a problem to find a collection of subsets which minimize the sum of costs of subset $W_j$ and it contains every element in $U$. For example, if $U = \{e_1,e_2,e_3,e_4,e_5$}, $S_1 = \{e_1,e_2$}, $S_2 = \{e_3,e_4$}, $S_3 = \{e_5$}, $S_4 = \{e_2,e_3$}, $S_5 = \{e_1$}, $S_6 = \{e_4$}, $W_1=10$, $W_2=10$, $W_3=1$, $W_4=15$, $W_5=1$, $W_6=1$. Optimal solution would be $W_3 + W_4 + W_5 + W_6 = 1 + 15 + 1 + 1 = 18$. Notice that $S_3 \cup S_4 \cup S_5 \cup S_6 = U$. However, it is known that $\operatorname{SET COVER}$ is a NP-hard. Which means that requires more than polynomial time if P $\neq$ NP.

ABA is a well-known problem at CAS based lock-free data structure. C++ supports std::atomic for abitrary data type but it isn’t sometimes lock free. You can check it with below.