呈之前的討論，對於 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)。
在 KTH 交換時選到的神課！想說把題解稍微紀錄一下 ✌️\
題目連結
前兩講討論的是給定起點，問到其他點的最短距離，稱為單源最短路徑問題，而現在我們想考慮 $V$ 中兩兩點對彼此間的最短距離，又稱全點對最短路徑問題。
呈前一講的討論，我們有了個求單源最短路徑的演算法Bellman-Ford (複雜度為 $\mathcal{O}(VE)$ )，現下我們考慮額外的限制條件(邊權重為非負)，想找出是否存在更有效率的演算法
圖的一個常見應用場合是想找出某兩點之間的最短(/長)路徑，此時的邊權重又視為兩節點之間的距離。
給定一張圖，要如何讀取當中的資訊呢？簡單來說就是從一給定點開始，依某種順序去拜訪相鄰(有關係)的點，最後走完所有點，收集完圖中的資訊。以下簡介兩種簡本的 traversal 方法以及應用。
Disjoint Set 顧名思義，代表了一群兩兩交集為空的集合們，常用於處理依據某種關係將元素們「分類」的問題。我們的目標是去 maintain collection of disjoint sets $S_1,S_2,\cdots,S_k$，而每個 $S_i$ (每個 category) 以一個代表值 (representative) 去紀錄。
有在使用 git 的人，應該都知道我們很多時候我們不希望 git 去 track 某些檔案，也不在意他們的改動情況(但有時候手滑還是會不小心 checkin 進去…😅)， 像是競賽的測資， c++ 編譯時的 .o 檔，binary executable 等等，這時候會加上 .gitignore 於工作目錄下達成我們的目的。
