layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # 🧠 Lecture 2e: Algorithmic Paradigms @luk036 👨‍💻 · 2026 📅 --- ## Overview 📋 - Greedy approach - Mathematical programming - Primal-dual algorithm - Randomized method - Dynamic programming - Local search - Simulated annealing - Books and online resource --- ### 🗺️ Algorithm Paradigms Flowchart .mermaid[ <pre> graph TD A[Algorithmic Paradigms] --> B[Greedy Approach] A --> C[Mathematical Programming] A --> D[Primal-Dual Algorithm] A --> E[Randomized Method] A --> F[Dynamic Programming] A --> G[Local Search] A --> H[Simulated Annealing] style A fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style B fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style C fill:#fff3e0,stroke:#e65100,stroke-width:3px style D fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px style E fill:#ffcdd2,stroke:#c62828,stroke-width:3px style F fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style G fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style H fill:#fff3e0,stroke:#e65100,stroke-width:3px </pre> ] --- ### 🤑 Greedy Approach - Excellent for Minimum Spanning Tree (MST) and Channel Routing Problem - Obtain optimal solution - Not bad for Knapsack problem - At least half of optimal solution - Very bad for Feedback Arc Removal problem - Even worse than a naïve method: randomly remove edges when traversing a graph, then reverses the set if $|{\color{lime}E'}|$ is greater than 0.5$|{\color{lime}E}|$. - Question: Any theory to predict the performance? --- ### Knapsack 🎒 Problem .pull-left[ - A thief considers taking ${\color{coral}b}$ pounds of loot 💰. The loot is in the form of ${\color{coral}n}$ items, each with weight ${\color{coral}a}_i$ and value ${\color{purple}p}_i$. Any amount of an item can be put in the knapsack as long as the weight limit ${\color{coral}b}$ is not exceeded ] .pull-right[  ] --- ### 🤑 Greedy Approach - Take as much of the item with the highest value per pound (${\color{purple}p}_i$/${\color{coral}a}_i$) as you can. If you run out of that item, take from the next highest (${\color{purple}p}_i$/${\color{coral}a}_i$) item. Continue until knapsack is full. --- ### 💻 Program 1: Greedy Knapsack - **Input**: Set of ${\color{coral}n}$ items, for each ${\color{darkblack}x}_i \in {\color{salmon}X}$, values ${\color{purple}p}_i$, ${\color{coral}a}_i$, positive integer ${\color{coral}b}$; - **Output**: Subset ${\color{salmon}Y} \subset {\color{salmon}X}$ such that $\sum {\color{coral}a}_i \leq {\color{coral}b}$; - Sort ${\color{salmon}X}$ in non-increasing order with respect to the ratio ${\color{purple}p}_i$/${\color{coral}a}_i$; - Let (${\color{darkblack}x}_1$, ${\color{darkblack}x}_2$, ..., ${\color{darkblack}x}_n$) be the sorted sequence - ${\color{salmon}Y}$ := $0$; - **for** ${\color{coral}i}$:=1 **to** ${\color{coral}n}$ **do** - **if** ${\color{coral}b} \geq {\color{coral}a}_i$ **do** - ${\color{salmon}Y}$ := ${\color{salmon}Y} \cup \{ {\color{darkblack}x}_i \}$; - ${\color{coral}b}$ := ${\color{coral}b} - {\color{coral}a}_i$; - **return** ${\color{salmon}Y}$ --- ### C++ code 🅒 ```{.cpp} template <class InputIt, typename T, typename F1, typename F2> InputIt greedy_knapsack(InputIt first, InputIt last, const T& b, F1&& price, F2&& weight) { using Item = typename InputIt::value_type; std::sort(first, last, [&](const Item& i1, const Item& i2) { return weight(i1) * price(i2) < weight(i2) * price(i1); }); T init(0); InputIt it = std::find_if(first, last, [&](Item& i) { return (init += weight(i)) > b; }); return it; } ``` - Test program can be found in <http://ideone.com/9ZK6ol>. --- ### 🤔 Can the thief do better? - Theorem 1. Let ${\color{purple}m}_H({\color{darkblack}x}) = \max({\color{purple}p}_{\max}, {\color{purple}m}_{GR}({\color{darkblack}x}))$, where ${\color{purple}p}_{\max}$ is the maximum profit of an item 💍 in ${\color{darkblack}x}$. Then ${\color{purple}m}_H({\color{darkblack}x})$ satisfies the following inequality: ${\color{purple}m}({\color{darkblack}x})/{\color{purple}m}_H({\color{darkblack}x}) < 2$. (p.42) (${\color{purple}m}({\color{darkblack}x})$ is the optimal solution) - As a consequence of the above theorem, a simple modification of Program 1 allows us to obtain a provably better algorithm. - HW: Implement the algorithm using C++ Template technique and iterators (generic programming style) --- ### ➗ Linear Programming Relaxation - Formulate a problem as an integer linear program. - By relaxing the integrality constraints we obtain a new linear program, whose optimal solution can be found in polynomial time. - This solution, in some cases, can be used to obtain a feasible solution for the original integer linear program, by "rounding" the values of the variables that do not satisfy the integrality constraints. --- ### 🎯 Weighted Vertex Cover - Given a weighted graph $G=({\color{salmon}V}, {\color{lime}E})$, Minimum Weighted Vertex Cover (MWVC) can be formulated as the following integer program ILP_VC($G$): - Minimize $\sum_{vi \in {\color{salmon}V} } {\color{coral}c_i} {\color{darkblack}x}_i$ - Subject to ${\color{darkblack}x}_i + {\color{darkblack}x}_j \geq 1$ for all $({\color{salmon}v_i}, {\color{salmon}v_j}) \in {\color{lime}E}$ - ${\color{darkblack}x}_i \in \{0, 1\}$ for all ${\color{salmon}v_i} \in {\color{salmon}V}$ --- ### 🔢 Program 2.6 Rounding WVC - **Input** Graph $G=({\color{salmon}V}, {\color{lime}E})$ with non-negative vertex weights; - **Output** Vertex cover ${\color{salmon}V'}$ of $G$; - Let ILP_VC be the linear integer programming formulation of the problem; - Let LP_VC be the problem obtained from ILP_VC by relaxing the integrality constraints; - Let ${\color{darkblack}x}(G^*)$ be the optimal solution for LP_VC; - ${\color{salmon}V'}$ := \{$v \mid {\color{darkblack}x}_v(G^*) \geq 0.5$\}; - **return** ${\color{salmon}V'}$ --- ### 📐 Linear Programming - Theorem 2.15. Given a graph $G$ with non-negative vertex weights, Program 2.6 finds a feasible solution of MWVC with value ${\color{purple}m}_{LP}(G)$ such that ${\color{purple}m}_{LP}(G)/{\color{purple}m}(G^*) \leq 2$. - Problem: need to solve the LP optimally. --- ### ☯ Primal-dual WVC - **Input** Graph $G = ({\color{salmon}V}, {\color{lime}E})$ with non-negative vertex weights; - **Output** Vertex cover ${\color{salmon}V'}$ of $G$; - Let DLP_VC be the dual of the LP relaxation of ILP_VC; - **for** each dual variable ${\color{firebrick}y}$ of DLP_VC **do** ${\color{firebrick}y} := 0$; - ${\color{salmon}V'} := 0$; - **while** ${\color{salmon}V'}$ is not a vertex cover **do** - Let $({\color{salmon}v_i}, {\color{salmon}v_j})$ be an edge not covered by ${\color{salmon}V'}$; - Increase ${\color{firebrick}y}_{ij}$ until a constraint of DLP_VC becomes tight; - **if** sum$({\color{firebrick}y_{ij}} | (i, j) \in {\color{lime}E} )$ is tight **then** - ${\color{salmon}V'} := {\color{salmon}V'} \cup \{{\color{salmon}v_i}\}$ (\* the i-th dual constraint is tight \*) - **else** - ${\color{salmon}V'} := {\color{salmon}V'} \cup \{{\color{salmon}v_j}\}$ (\* the j-th dual constraint is tight \*) - **return** ${\color{salmon}V'}$ --- ### ☯ Primal-dual WVC - Theorem 2.16. Given a graph $G$ with non-negative weights, Program 2.7 finds a feasible solution of MWVC such that ${\color{purple}m}_\text{PD}(G)/{\color{purple}m}(G^*) \leq 2$. (p. 69) - Much faster than Program 2.6 (only take linear time) because we don't need to solve the LP optimally. - Bonus: Sum of dual variables ${\color{firebrick}y}_{ij}$ gives the lower bound of the optimal solution. --- ### 🎲 Program - Random WVC - **Input** Graph $G= ({\color{salmon}V}, {\color{lime}E})$, weight function $w: {\color{salmon}V} \mapsto N$; - **Output** Vertex cover ${\color{salmon}U}$; - ${\color{salmon}U}$ := $\emptyset$; - **while** ${\color{lime}E}$ is not empty **do** - Select an edge ${\color{lime}e} = ({\color{salmon}v},{\color{salmon}t}) \in {\color{lime}E}$; - Randomly choose ${\color{darkblack}x}$ from $\{{\color{salmon}v},{\color{salmon}t}\}$ with Pr$\{{\color{darkblack}x}={\color{salmon}v}\}$ = ${\color{coral}w}({\color{salmon}t}) / ({\color{coral}w}({\color{salmon}v}) + {\color{coral}w}({\color{salmon}t}))$; - ${\color{salmon}U}$ := ${\color{salmon}U} \cup \{{\color{darkblack}x}\}$; - ${\color{lime}E}$ := ${\color{lime}E} - \{{\color{lime}e} \mid {\color{darkblack}x} \text{ is an endpoint of } {\color{lime}e}\}$ - **return** ${\color{salmon}U}$ --- ### 🎲 Randomized Algorithms - In many cases, a randomized algorithm is either simpler or faster (or both) than a deterministic algorithm. - However, it does not guarantee that the algorithm always finds a good approximation solution. - Theorem 5.1. The expect measure of the solution returned by the previous algorithm satisfied the following inequality: $$E[{\color{purple}m}_\text{RWVC}({\color{darkblack}x})] \leq 2 {\color{purple}m}^*({\color{darkblack}x})$$ - HW: Implement MWVC solvers using all the above methods. Also extend all the methods to handle hypergraph --- ### 🧮 Dynamic Programming (I) - One passenger wants to go from city A to city H through the _shortest path_ according to the map on the right, where number of indicate distance between corresponding cities. - Reference: Pablo Pedregal, _Introduction to Optimization_, chapter 5.8, Springer, 2003 --- ### 🧮 Dynamic Programming (II) - Proposition 5.24 (Fundamental property of dynamic programming) - If $S({\color{coral}t}_j, {\color{darkblack}x})$ denotes the optimal cost from $({\color{coral}t}_0, {\color{darkblack}x})$ to $({\color{coral}t}_j, {\color{darkblack}x})$ - then we must have S(${\color{coral}t}_{j+1}$, ${\color{firebrick}y}$) = min_j \[S(${\color{coral}t}_j$, ${\color{darkblack}x}$) + c(${\color{coral}j}$,${\color{darkblack}x}$,${\color{firebrick}y}$)\] --- ### 🧮 Dynamic Programming (III) - According to Proposition 5.24, we must proceed successively to determine S(${\color{coral}t}_j, {\color{darkblack}x}$) for each ${\color{darkblack}x}$ in A_j to end with S(${\color{coral}t}_n, {\color{darkblack}x}_n$). In the proposed example, we have four stages ${\color{coral}t}_0$, ${\color{coral}t}_1$, ${\color{coral}t}_2$, ${\color{coral}t}_3$ with associated sets of feasible states - A₀ = {A}, A₁ = {B, C, D}, A₂ = {E,F,G}, A₃ = {H} - For each city in A₁, there is a unique path from A, so that it must be optimal, and - S(${\color{coral}t}_1$, B) = 7, S(${\color{coral}t}_1$, C) = 4, S(${\color{coral}t}_1$, D) = 1. - For each city in A₂, we determine the optimal cost based on the fundamental property of dynamic programming, - S(${\color{coral}t}_{j+1}$, ${\color{firebrick}y}$) = min_j \[S(${\color{coral}t}_j$, ${\color{darkblack}x}$) + c(${\color{coral}j}$,${\color{darkblack}x}$,${\color{firebrick}y}$)\] --- ### 🔍 Local Search - **Input**: Instance ${\color{darkblack}x}$; - **Output**: Solution ${\color{darkblack}s}$ - ${\color{darkblack}s}$ := initial feasible solution ${\color{darkblack}s_0}$; - (\* $\mathcal{N}$ denotes the neighborhood function \*) - **repeat** - Select any ${\color{darkblack}s'} \in \mathcal{N}(x, {\color{darkblack}s})$ not yet considered; - **if** ${\color{purple}m}(x,{\color{darkblack}s'})$ < ${\color{purple}m}(x, {\color{darkblack}s})$ **then** - ${\color{darkblack}s}$ := ${\color{darkblack}s'}$; - **until** all solutions in $\mathcal{N}(x, {\color{darkblack}s})$ have been visited; - **return** ${\color{darkblack}s}$; --- ### ❄️ Simulated Annealing - **Input**: Instance ${\color{darkblack}x}$; - **Output**: Solution ${\color{darkblack}s}$ - ${\color{brown}\tau}$ := ${\color{coral}t}$; - ${\color{darkblack}s}$ := initial feasible solution ${\color{darkblack}s_0}$; - **repeat** - **for** ${\color{coral}l}$ times **do** - Select any unvisited ${\color{darkblack}s'} \in \mathcal{N}(x, {\color{darkblack}s})$ - **if** (${\color{purple}m}(x, {\color{darkblack}s'})$ < ${\color{purple}m}(x, {\color{darkblack}s})$) - ${\color{darkblack}s}$ := ${\color{darkblack}s'}$; - **else** - ${\color{coral}δ}$ := ${\color{purple}m}(x, {\color{darkblack}s'}) - {\color{purple}m}(x, {\color{darkblack}s})$; - ${\color{darkblack}s}$ := ${\color{darkblack}s'}$ with probability exp($-{\color{coral}δ}/{\color{coral}t}$); - ${\color{brown}\tau}$ := ${\color{coral}r} \cdot {\color{brown}\tau}$; (\* update of temperature \*) - **until** FROZEN; - **return** $s$; --- ### 🧪 Other Heuristic Methods - 🧗 Hill Climbing - Reference: _Hill Climbing_ by R. A. Sutton and A. G. Barto, MIT Press, 1983 - 🐜 Ant Colony Optimization (ACO) - Reference: _Ant Colony Optimization_, D. E. Kirkpatrick, C. Storn, Journal of Global Optimization, 1992 - 🧬 Genetic Algorithm (GA) - Reference: _Genetic Algorithms_, M. Mitchell, McGraw Hill, 1989 - 🙅 Tabu Search (TS) - Reference: _Tabu search_, Kirkpatrick, Storn, 1983 - Variable Neighborhood Descent (VND) - Reference: _Variable neighborhood descent_, Kirkpatrick, Storn, 1983 --- ## 📚 Books and Online Resources - G. Ausiello et al. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999. (O224 C737) - M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, 1979. - Pablo Pedregal. Introduction to Optimization. Springer, 2003 (O224 P371) --- count: false class: nord-dark, middle, center .pull-left[ # Q&A 🎤 ] .pull-right[  ]