在 第一講中，我們證明了有很高的機率，任意 slot 中 element 的個數均為 $\mathcal{\Theta}(\frac{\ln n}{\ln (\ln n)})$ ，而這一講想討論的是，如果今天我們手上有兩個 hash function (from same $\mathcal{H}$)可以選，每次我們就看哪一個 $h$ 回傳的 slot 中元素比較少，就將 element hash 到 slot，那麼現在 $\mathbb{E}[, \text{max num of elements in any slots} , ]$ ?
Hashing 的一個 criteria 是希望儘可能不要發生 collision (也就是 Worst Case 也在 $\mathcal{O}(1)$ lookup)，今天假設我們已知元素的個數，該如何設計一個 hash function 使得不會有任何 collition 發生？
前面提到過一個較為複雜的優化問題， Metric Facility Location Problem ，並給出了一個 4-Approx. Algorithm ，於這講中，我們要來利用前面提到的 Primal-Dual method 來設計演算法。
呈之前的討論，對於 WSC 問題，我們有了利用 LP solver 去對解做 deterministic rounding 及 randomized rounding 的演算法，解法的共通點是必須要先 run 過 LP solver (雖然理論上是 POLY ，實務上現行的 solver 也很有效率)，但我們仍想問說，是否存在不須使用 LP solver 的演算法呢？ 而這也是這講所要提到的 Primal-Dual Method 。
接續前面幾講，一個常用的技巧是，利用 LP solver 得出來的解 $\mathbf{x}^{\star}$， 拿去做 rounding 推出原先問題的解 $\mathbf{x}^{\prime}$ (with 一個還不錯的 approx. ratio)。而這講會講述一個較為複雜的問題 - Metric Facility Location Problem (MFL)。
呈前一講，我們對有限制的 WSC 問題有 $l$-approx. algorithm，但可能並不是太好(比方說 $l=|U|$ 之類)，於是我們嘗試引進一些隨機性，雖然犧牲了 deterministic 的 approx. ratio ，有時候甚至會得到更爛的結果(甚至不滿足 constraint @@)，但可以證明在大部分時候，都可以得到一個還不錯 (approx. ratio ISN'T too bad)的結果。
這一講會展示將問題轉化為線性規劃的 form (但可能是 ILP)，利用 LP solver 得到解，做 LP relaxation 並證明這個解不會太差 (approx. ratio 不太大)。
**Definition:**
A linear programming is a problem of maximizing or minimizing a linear
multivariate function subject to some linear constraints
從前兩講關於分配 (在一堆物品中，決定哪些是要拿的一群，哪些不拿) 的最佳化問題中，我們延伸出新的問題，Bin Packing Problem。不同於在 Knapsack Problem 中，我們只有一個箱子(可以想成你聘了一個工人搬一個箱子)；在Bin Packing 問題中，要取走所有寶物(所有寶物的重量都小於 1 單位)，而你需要聘請一些工人來搬，但今天每個工人都只帶了一個負重為 1 單位的箱子，該如何分配這些寶物(雖說是寶物，但其實我們不care價值惹)，使得需帶的箱子(聘請的工人)為最少？
簡單的 formulation 如下：
Subset Sum Problem 與 Knapsack Problem 相同，也是一個 NPC 問題(可以想成 Knapsack Problem weight 均為 1 的特例)。而在 Knapsack Problem 中，我們發展出等差 的rounding 技巧，犧牲精確度去換取更低的時間複雜度，而這一講中，將利用等比的方式去做 rounding 。
背包問題為一個典型的最佳化問題，想像你來到了一個寶庫，裡頭有一些寶物，都有各自的價值和重量，但你只帶了一個背包(而且負重還有限制)，要怎麼取寶物才能在背得走的前提下，帶走價值總和儘可能高的寶物們呢？
這裡我們考慮最基本的 0/1 - Knapsack Problem 。簡單的 formulation 如下:
Hashing 可以想成是一種 renaming 的方式，原先的名字 (key) 可能很長，但可能的組合並不完全隨機，且數量相對整個宇集少上不少，若我們要建立一個跟宇集一樣大的 Hash Table 並不符合成本(且大部份 slot 是空的)，所以想透由 Hashing 的方式，重新命名 key’ ，並依據 key’ 將資料放到 size 跟資料個數差不多的 Hash Table 中。
