layout: true class: typo, typo-selection --- class: nord-dark, middle, center # Lecture 2e: Algorithmic Paradigms @luk036 👨‍💻 · 2026 📅 --- ## 📝 Abstract Throughout this lecture, we'll examine various approaches to solving computational problems, from greedy algorithms to simulated annealing. Each paradigm offers unique advantages and limitations that make them suitable for different problem domains. We'll analyze how these paradigms perform on classic problems like the Knapsack Problem and Weighted Vertex Cover, and provide implementation insights using modern programming techniques. By the end of this lecture, you'll have a deeper understanding of when and how to apply these powerful algorithmic tools. --- ### Overview 📋 - Greedy approach - Mathematical programming - Primal-dual algorithm - Randomized method - Dynamic programming - Local search - Simulated annealing - Books and online resource --- ### Algorithmic Paradigms .mermaid[ <pre> graph TD AP[Algorithmic Paradigms] AP --> G[Greedy] AP --> DP[Dynamic Programming] AP --> LP[Linear Programming] AP --> PD[Primal-Dual] AP --> R[Randomized] AP --> LS[Local Search] style AP fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style G fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px style DP fill:#e3f2fd,stroke:#1565c0,stroke-width:3px style LP fill:#fff3e0,stroke:#e65100,stroke-width:3px style PD fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px style R fill:#ffcdd2,stroke:#c62828,stroke-width:3px style LS fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px </pre> ] --- ### Algorithmic Approaches Overview - Diverse Problem-Solving Strategies From greedy approaches to mathematical programming, each paradigm offers unique advantages for specific problem domains. - Implementation Techniques Modern programming approaches like generic programming enhance flexibility and performance across algorithm implementations. - Theoretical Foundations Understanding the mathematical underpinnings helps predict algorithm performance and limitations. --- ### 🤑 The Greedy Approach The greedy approach makes locally optimal choices at each step, hoping to find a global optimum. While this works perfectly for some problems, it can fail dramatically for others. - Excellent for Minimum Spanning Tree (MST) Achieves optimal solutions for MST and Channel Routing Problems - Decent for Knapsack problem Guarantees at least half of the optimal solution value - Poor for Feedback Arc Removal problem Performs worse than even naive random methods: randomly remove edges when traversing a graph, then reverses the set if $|{\color{lime}E'}|$ is greater than 0.5$|{\color{lime}E}|$. The key question remains: can we predict when greedy algorithms will perform well? --- ### 🎒 Knapsack Problem .pull-left[ - Problem Definition A thief considers taking ${\color{coral}b}$ pounds of loot 💰. The loot consists of ${\color{coral}n}$ items, each with weight ${\color{coral}a_i}$ and value ${\color{coral}p_i}$. Any amount of an item can be taken as long as the weight limit ${\color{coral}b}$ is not exceeded. - The greedy approach The greedy approach takes items in order of highest value-to-weight ratio (${\color{coral}p_i}/{\color{coral}a_i}$) until the knapsack is full. ] .pull-right[  ] --- ### Program 1: Greedy Knapsack - **Input**: Set of ${\color{coral}n}$ items, for each ${\color{green}x_i} \in {\color{salmon}X}$, values ${\color{coral}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{coral}p_i}$/${\color{coral}a_i}$; - Let (${\color{green}x_1}$, ${\color{green}x_2}$, ..., ${\color{green}x_n}$) be the sorted sequence - ${\color{salmon}Y}$ := $0$; - **for** $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{green}x_i} \}$; - ${\color{coral}b}$ := ${\color{coral}b} - {\color{coral}a_i}$; - **return** ${\color{salmon}Y}$ --- ### C++ Template Implementation ```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>. --- ### Why Generic Programming - 🤸 Increased Flexibility Adapt code to various data types without modification, allowing the same algorithm to work with different problem instances. - ♻️ Reduced Duplication Write once, use for multiple types, significantly reducing development and maintenance effort. - 🛡️ Enhanced Type Safety Catch errors at compile-time rather than runtime, improving reliability and reducing debugging time. - 🚀 Improved Performance Optimize code for specific types at compile-time, eliminating runtime overhead of virtual functions or type checking. --- ### Can the thief do better? - Theorem 1 Let m_H(${\color{green}x}$) = max(${\color{coral}p}$_max, m_GR(${\color{green}x}$)), where ${\color{coral}p}$_max is the maximum profit of an item 💍 in ${\color{green}x}$. Then m_H(${\color{green}x}$) satisfies the inequality: m(${\color{green}x}$)/m_H(${\color{green}x}$) < 2. (p.42) (m(${\color{green}x}$) is the optimal solution) - Performance Guarantee 💯 Theorem 1 states that if we take the maximum of the greedy solution and the highest-value single item, we achieve a solution that is at least half of the optimal value. This hybrid approach provides a provable performance bound, making it a reliable choice for practical implementations. HW: Implement the algorithm using C++ Template technique and iterators (generic programming style) --- ### Mathematical Programming Approaches - Integer Linear Programming Exact formulation with integer constraints - LP Relaxation Remove integrality constraints for polynomial-time solving - Primal-Dual Method Iteratively improve both primal and dual solutions Mathematical programming provides a powerful framework for solving optimization problems. By relaxing integer constraints, we can solve problems in polynomial time, then round the solution to obtain approximate integer solutions. The primal-dual method offers a faster alternative that doesn't require solving the LP optimally while still providing performance guarantees. --- ### Weighted Vertex Cover Problem - ILP Formulation 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$): $$\begin{array}{lll} \text{minimize} & \sum_{v \in {\color{salmon}V} } {\color{coral}c_v} {\color{green}x_v} \\ \text{subject to} & {\color{green}x_u} + {\color{green}x_v} \geq 1 & \forall (u, v) \in {\color{lime}E} \\ & {\color{green}x_v} \in \{0, 1\} & \forall v \in {\color{salmon}V} \end{array}$$ - LP Relaxation Relax integrality constraints for polynomial-time solving - Rounding Approach Round variables ≥ 0.5 to 1, guaranteeing 2-approximation. --- ### 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{green}x}(G^*)$ be the optimal solution for LP_VC; - ${\color{salmon}V'}$ := \{$v \mid {\color{green}x_v}(G^*) \geq 0.5$\}; - **return** ${\color{salmon}V'}$ --- ### LP Relaxation - Theorem 2.15. Given a graph $G$ with non-negative vertex weights, Program 2.6 finds a feasible solution of MWVC with value m_LP($G$) such that m_LP($G$)/m($G^*$) $\leq 2$. Problem: need to solve the LP optimally. - Primal-Dual Method Linear-time algorithm with 2-approximation guarantee --- ### ☯ 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 $m_\text{PD}(G)/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. --- ### 🎲 Randomized Algorithms Randomized algorithms introduce probability to achieve simpler or faster solutions. For Weighted Vertex Cover, the randomized approach selects edges and endpoints with probability proportional to weights, achieving an expected 2-approximation ratio. These algorithms don't guarantee good solutions every time but perform well on average. --- ### 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{green}x}$ from $\{{\color{salmon}v},{\color{salmon}t}\}$ with Pr$\{{\color{green}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{green}x}\}$; - ${\color{lime}E}$ := ${\color{lime}E} - \{{\color{lime}e} \mid {\color{green}x} \text{ is an endpoint of } {\color{lime}e}\}$ - **return** ${\color{salmon}U}$ --- ### 🎲 Randomized Algorithms - Theorem 5.1. The expect measure of the solution returned by the previous algorithm satisfied the following inequality: $$E[m_\text{RWVC}({\color{green}x})] \leq 2 m^*({\color{green}x})$$ HW: Implement MWVC solvers using all the above methods. Also extend all the methods to handle hypergraph. --- ### Dynamic Programming (I) - Dynamic programming solves problems by breaking them into overlapping subproblems. - This approach works by solving subproblems once and storing their solutions to avoid redundant computation. - 📚 Example: 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{green}x})$ denotes the optimal cost from $({\color{coral}t_0}, {\color{green}x})$ to $({\color{coral}t_j}, {\color{green}x})$ - then we must have S(${\color{coral}t_{j+1}}$, ${\color{green}y}$) = min_j \[S(${\color{coral}t_j}$, ${\color{green}x}$) + c($j$,${\color{green}x}$,${\color{green}y}$)\] --- ### Dynamic Programming (III) - According to Proposition 5.24, we must proceed successively to determine S(${\color{coral}t_j}, {\color{green}x}$) for each ${\color{green}x}$ in A_j to end with S(${\color{coral}t_n}, {\color{green}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{green}y}$) = min_j \[S(${\color{coral}t_j}$, ${\color{green}x}$) + c($j$,${\color{green}x}$,${\color{green}y}$)\] --- ### Local Search and Simulated Annealing - ⌕ Local Search Iteratively improve by exploring neighboring solutions - 🌡 Simulated Annealing Accept worse solutions with decreasing probability over time Local search methods explore the solution space by moving between neighboring solutions. While basic local search can get trapped in local optima, simulated annealing introduces randomness that allows occasional uphill moves, helping escape local minima. The algorithm gradually reduces the probability of accepting worse solutions, eventually converging to a good solution. --- ### ⌕ Local Search - **Input**: Instance ${\color{green}x}$; - **Output**: Solution ${\color{green}s}$ - ${\color{green}s}$ := initial feasible solution ${\color{green}s_0}$; - (\* $\mathcal{N}$ denotes the neighborhood function \*) - **repeat** - Select any ${\color{green}s'} \in \mathcal{N}(x, {\color{green}s})$ not yet considered; - **if** $m(x,{\color{green}s'})$ < $m(x, {\color{green}s})$ **then** - ${\color{green}s}$ := ${\color{green}s'}$; - **until** all solutions in $\mathcal{N}(x, {\color{green}s})$ have been visited; - **return** ${\color{green}s}$; --- ### 🌡 Simulated Annealing - **Input**: Instance ${\color{green}x}$; - **Output**: Solution ${\color{green}s}$ - ${\color{coral}τ}$ := ${\color{coral}t}$; - ${\color{green}s}$ := initial feasible solution ${\color{green}s_0}$; - **repeat** - **for** ${\color{coral}l}$ times **do** - Select any unvisited ${\color{green}s'} \in \mathcal{N}(x, {\color{green}s})$ - **if** ($m(x, {\color{green}s'})$ < $m(x, {\color{green}s})$) - ${\color{green}s}$ := ${\color{green}s'}$; - **else** - ${\color{coral}δ}$ := $m(x, {\color{green}s'}) - m(x, {\color{green}s})$; - ${\color{green}s}$ := ${\color{green}s'}$ with probability exp($-{\color{coral}δ}/{\color{coral}t}$); - ${\color{coral}τ}$ := ${\color{coral}r} \cdot {\color{coral}τ}$; (\* update of temperature \*) - **until** FROZEN; - **return** ${\color{green}s}$; --- ### Other Heuristic Methods - 🧗 Hill Climbing - Reference: _Hill Climbing_ by Sutton and 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 To deepen your understanding of algorithmic paradigms, explore these valuable resources: - Complexity and Approximation G. Ausiello et al., Springer, 1999 - Covers combinatorial optimization problems and their approximability properties. - Computers and Intractability M. R. Garey and D. S. Johnson, Freeman, 1979 - The definitive guide to the theory of NP-completeness. - Introduction to Optimization Pablo Pedregal, Springer, 2003 - Provides fundamental concepts and techniques in optimization theory. --- count: false class: nord-dark, middle, center .pull-left[ # Q&A 🎤 ] .pull-right[  ]