layout: true class: typo, typo-selection --- count: false class: nord-dark, middle, center # ☯ Primal-Dual Method for Approximation Algorithms @luk036 2024-11-20 [](https://netlistx.readthedocs.io/en/latest/?badge=latest) [](https://codecov.io/gh/luk036/netlistx) --- ## 📝 Abstract The primal-dual method is a powerful technique in the field of approximation algorithms. Originating from linear programming and combinatorial optimization, it has been adapted to tackle NP-hard problems effectively. This lecture explores the fundamentals, methodology, and applications of this versatile approach, demonstrating its significance in developing efficient solutions for complex computational challenges that would otherwise be intractable. --- ## Fundamentals of the PD Method - Dual Approach: The primal-dual method considers both the primal integer programming formulation and the dual of its LP relaxation. This dual perspective provides valuable insights into the problem structure. - Iterative Improvement: Starting with a dual feasible solution, the method iteratively improves while constructing a primal integral solution. This process often leads to dual-ascent algorithms. - Relaxed Conditions: For NP-hard problems, the method relaxes complementary slackness conditions, allowing for efficient approximation algorithms with provable guarantees. --- ## Example: Vertex Cover - Instance: A graph $G = (V, E)$ - Solution: A vertex cover for $G$, i.e., a subset $U$ such that, for each edge $(u,v) \in E$, at least one of $u$ and $v$ belongs to $U$ - Measure: Cardinality of the vertex cover, i.e. $|U|$ - Bad News: APX-complete. - Comment: Admits a PTAS for *planar* graphs [Baker, 1994]. The generalization to $k$-hypergraphs, for $k>1$, is approximable within $k$ [Bar-Yehuda and Even, 1981] and [Hochbaum, 1982a]. - Garey and Johnson: GT1 --- ## Greedy-Vertex-Cover ``` ┌─┬─────────────────────────────────────────┐ │1│U = {} │ │2│do chose v in V with max. degree │ │3│ U = U + {v} │ │4│ remove v and every edge adjacent to v│ │5│until all edges covered │ │6│return U │ └─┴─────────────────────────────────────────┘ ``` Requirements: - Need a (bucket) heap to maintain max. degree - Only for unweighted problems. --- ## Weighted Vertex Cover (WVC) The Weighted Vertex Cover problem extends the basic vertex cover by assigning weights to vertices. - Instance: $G = (V, E)$ with non-negative vertex weights $w: V ↦ N$ - Solution: A vertex cover for $G$, i.e., a subset $U$ such that, for each edge $(u,v) ∈ E$, at least one of $u$ and $v$ belongs to $U$  This problem has applications in network monitoring, resource allocation, and conflict resolution in scheduling. --- ## Mathematical Formulation of WVC ILP Formulation: $$\begin{array}{lll} \text{minimize} & \sum_{v \in V} w_v x_v \\ \text{subject to} & x_u + x_v \geq 1, & \forall (u, v) \in E \\ & x_v \in \{0, 1\}, & \forall v \in V \end{array}$$ LP Relaxation: .pull-left[ Primal LP: $$\begin{array}{lll} \text{min} & \sum_{v \in V} w_v x_v \\ \text{s.t.} & x_u + x_v \geq 1, & \forall (u, v) \in E \\ & 0 \leq x_v \leq 1, & \forall v \in V \end{array}$$ ] .pull-right[ Dual LP: $$\begin{array}{lll} \text{max} & \sum_{e \in E} y_e \\ \text{s.t.} & \sum_{e \in \text{adj}(v)} y_e \leq w_v, & \forall v \in V \\ & y_e \geq 0, & \forall e \in E \end{array}$$ ] --- ## Primal-Dual Algorithm for WVC - Initialize Set all dual variables to zero. Start with empty vertex cover $U$. - Find Uncovered Edge Locate an edge $e=(u,v)$ not yet covered by $U$. - Increase Dual Variable Increase $y_e$ until a dual constraint becomes tight. - Add Vertex Add the vertex with tight constraint to the cover $U$. --- ## Primal-dual WVC - **Input** Graph $G = (V, E)$ with non-negative vertex weights $w$; - **Output** Vertex cover $U$ of $G$; - Let DLP_VC be the dual of the LP relaxation of ILP_VC; - ~~**for** each dual variable $y$ of DLP_VC **do** $y$ := 0;~~ - $U := 0$; - **while** $U$ is not a vertex cover **do** - Let $e = (u, v)$ be an edge not covered by $U$; - Increase $y_e$ until a constraint of DLP_VC becomes tight; - **if** $\sum_{e \in E} y_{e}$ is tight **then** - $U := U \cup \{u\}$ - **else** - $U := U \cup \{v\}$ - **return** $U$ --- ## Python Implementation ```python def min_vertex_cover(ugraph, weight, coverset = None): if coverset is None: coverset = set() total_dual_cost = 0 # for assertion total_prml_cost = 0 gap = copy.copy(weight) for utx, vtx in ugraph.edges(): if utx in coverset or vtx in coverset: continue if gap[utx] < gap[vtx]: utx, vtx = vtx, utx # swap coverset.add(vtx) total_dual_cost += gap[vtx] total_prml_cost += weight[vtx] gap[utx] -= gap[vtx] gap[vtx] = 0 assert total_dual_cost <= total_prml_cost return coverset, total_prml_cost ``` --- ## General Methodology 1. Formulate as Integer Program: Begin by expressing the problem as an integer programming formulation, capturing the essential constraints and objectives. 2. Consider LP Relaxation Dual: Analyze the dual of the linear programming relaxation, which provides a lower bound on the optimal solution. 3. Iterative Improvement: Incrementally increase dual variables while constructing a primal solution, ensuring feasibility and optimality conditions are maintained. 4. Approximation Analysis: Evaluate the approximation ratio based on the relationship between the constructed primal and dual solutions. --- ## Key Strengths of the PD Method - Provable Approximation Guarantees 💯: The method provides mathematically rigorous bounds on solution quality, ensuring reliable performance. - Combinatorial Algorithms: Often leads to efficient combinatorial algorithms, avoiding the need for solving large linear programs. - Problem Structure Insights: Offers deep insights into the underlying structure of complex optimization problems. - Wide Applicability: Suitable for a broad range of NP-hard problems across various domains of computer science and operations research. --- ## Generic PD for Cover Problems 1. Initialize: Begin with an empty solution set $A$ and set all dual variables $y$ to 0. 2. Iterate: While the solution A is not feasible, identify violated connectivity requirements, increase corresponding dual variables, and add edges to $A$ when dual constraints become tight. 3. Prune: Remove unnecessary edges from $A$ to optimize the final solution. 4. Return Solution Output the optimized solution with provable approximation guarantees based on the relationship between primal and dual values. --- ## Python Implementation ```python def pd_cover( violate: Callable, weight, soln: Set ) -> Tuple[Set, Union[int, float]]: total_prml_cost = 0 total_dual_cost = 0 gap = copy.copy(weight) for S in violate(): min_vtx = min(S, key=lambda vtx: gap[vtx]) min_val = gap[min_vtx] soln.add(min_vtx) total_prml_cost += weight[min_vtx] total_dual_cost += min_val for vtx in S: gap[vtx] -= min_val assert total_dual_cost <= total_prml_cost return soln, total_prml_cost ``` --- ## Example: WVC for Hypergraph A hypergraph extends the concept of a graph by allowing edges to connect any number of vertices. The vertex cover problem for hypergraphs requires finding a minimum weight set of vertices that intersects with every hyperedge, making it more complex than the standard graph version. - Instance: $H = (V, E)$ with non-negative vertex weights $w: V ↦ N$ - Solution: A vertex cover for $H$, i.e., a subset $U$ such that, for each edge $e ∈ E$, at least one of adj($e$) belongs to $U$  --- ## Mathematical Formulation of WVC ILP Formulation: $$\begin{array}{lll} \text{minimize} & \sum_{v \in V} w_v x_v \\ \text{subject to} & \sum_{v \in \text{adj}(e)} x_v \geq 1, & \forall e \in E \\ & x_v \in \{0, 1\}, & \forall v \in V \end{array}$$ LP Relaxation: .pull-left[ Primal LP: $$\begin{array}{lll} \text{min} & \sum_{v \in V} w_v x_v \\ \text{s.t.} & \sum_{v \in \text{adj}(e)} x_v \geq 1, & \forall e \in E \\ & 0 \leq x_v \leq 1, & \forall v \in V \end{array}$$ ] .pull-right[ Dual LP: $$\begin{array}{lll} \text{max} & \sum_{e \in E} y_e \\ \text{s.t.} & \sum_{e \in \text{adj}(v)} y_e \leq w_v, & \forall v \in V \\ & y_e \geq 0, & \forall e \in E \end{array}$$ ] --- ## Python Implementation ```python def min_hyper_vertex_cover( hgr, weight, coverset = None ) -> Tuple[Set, Union[int, float]]: if coverset is None: coverset = set() def violate_netlist() -> Generator: for net in hyprgraph.nets: if any(v in coverset for v in hgr.ugraph[net]): continue yield hyprgraph.ugraph[net] return pd_cover(violate_netlist, weight, coverset) ``` --- ## Weighted Cycle Cover (WCC) Find a minimum weight set of vertices that intersects with every cycle in the graph. This problem has applications in breaking feedback loops in systems and ensuring acyclic dependencies. - Instance: $G = (V, E)$ with non-negative vertex weights $w: V ↦ N$ - Define: a cycle $c$ is a subset of $V$ ... , $C$ is a set of all cycles - Solution: A vertex cover for $G$, i.e., a subset $U$ such that, for each cycle $c ∈ C$, at least one of vertices belongs to $U$  --- ## Mathematical Formulation of WCC ILP Formulation: $$\begin{array}{lll} \text{minimize} & \sum_{v \in V} w_v x_v \\ \text{subject to} & \sum_{v \in c} x_v \geq 1, & \forall c \in C \\ & x_v \in \{0, 1\}, & \forall v \in V \end{array}$$ LP Relaxation: .pull-left[ Primal LP: $$\begin{array}{lll} \text{min} & \sum_{v \in V} w_v x_v \\ \text{s.t.} & \sum_{v \in c} x_v \geq 1, & \forall c \in C \\ & 0 \leq x_v \leq 1, & \forall v \in V \end{array}$$ ] .pull-right[ Dual LP: $$\begin{array}{lll} \text{max} & \sum_{c \in C} y_c \\ \text{s.t.} & \sum_{c: v \in c} y_c \leq w_v, & \forall v \in V \\ & y_c \geq 0, & \forall c \in C \end{array}$$ ] --- ## Python Implementation ```python def min_cycle_cover( ugraph: nx.Graph, weight, coverset = None ) -> Tuple[Set, Union[int, float]]: if coverset is None: coverset = set() def find_cycle(): for info, parent, child in _generic_bfs_cycle( ugraph, coverset): return _construct_cycle(info, parent, child) def violate() -> Generator: while True: S = find_cycle() if S is None: break yield S return pd_cover(violate, weight, coverset) ``` --- ## Weighted Odd Cycle Cover Find a minimum weight set of vertices that intersects with every odd-length cycle. This problem is equivalent to making a graph bipartite by removing vertices and has applications in conflict resolution. - Instance: $G = (V, E)$ with non-negative vertex weights $w: V ↦ N$ - Define: an odd cycle $c$ is a subset of $V$ ... , $C_\text{odd}$ is a set of all odd cycles - Solution: A vertex cover for $G$, i.e., a subset $U$ such that, for each odd cycle $c ∈ C_\text{odd}$, at least one of vertices belongs to $U$  --- ## Mathematical Formulation ILP Formulation of WOCC: $$\begin{array}{lll} \text{minimize} & \sum_{v \in V} w_v x_v \\ \text{subject to} & \sum_{v \in c} x_v \geq 1, & \forall c \in C_\text{odd} \\ & x_v \in \{0, 1\}, & \forall v \in V \end{array}$$ LP Relaxation: .pull-left[ Primal LP: $$\begin{array}{lll} \text{min} & \sum_{v \in V} w_v x_v \\ \text{s.t.} & \sum_{v \in c} x_v \geq 1, & \forall c \in C_\text{odd} \\ & 0 \leq x_v \leq 1, & \forall v \in V \end{array}$$ ] .pull-right[ Dual LP: $$\begin{array}{lll} \text{max} & \sum_{c \in C_\text{odd}} y_c \\ \text{s.t.} & \sum_{c: v \in c} y_c \leq w_v, & \forall v \in V \\ & y_c \geq 0, & \forall c \in C_\text{odd} \end{array}$$ ] --- ## Python Implementation ```python def min_odd_cycle_cover( ugraph, weight, coverset = None ) -> Tuple[Set, Union[int, float]]: if coverset is None: coverset = set() def find_odd_cycle(): for info, parent, child in _generic_bfs_cycle( ugraph, coverset): _, depth_child = info[child] _, depth_parent = info[parent] if (depth_parent - depth_child) % 2 == 0: return _construct_cycle(info, parent, child) def violate() -> Generator: while True: S = find_odd_cycle() if S is None: break yield S return pd_cover(violate, weight, coverset) ``` --- ## Applications in EDA WOCC is used in Electronic Design Automation for Double Patterning Lithography (DPL) combined with E-beam lithography, solving coloring conflicts in semiconductor manufacturing.  ---  --- ## Weighted Maximal Matching (WMM) for Hypergraph - Instance: $H = (V, E)$ with non-negative vertex weights $w: V ↦ N$  --- ## LP Relaxation of WMM Primal LP: $$\begin{array}{lll} \text{min} & \sum_{e \in E} w_e x_e \\ \text{s.t.} & \sum_{e \in \text{adj}(v)} x_e \leq 1, & \forall v \in V \\ & x_e + \sum_{v \in \text{adj}(e)} \sum_{f \in \text{adj}(v)} x_f \geq 1, & \forall e \in E \\ & 0 \leq x_v \leq 1, & \forall v \in V \end{array}$$ Dual LP: $$\begin{array}{lll} \text{max} & \sum_{e \in E} y_e - \sum_{v \in V} z_v \\ \text{s.t.} & y_e + \sum_{v \in \text{adj}(e)} (-z_v + \sum_{f \in \text{adj}(v)} y_f) \leq w_e, & \forall e \in E \\ & y_e \geq 0, & \forall e \in E \\ & z_v \geq 0, & \forall v \in V \end{array}$$ --- ## Other Applications and Extensions - 𖣂 Steiner Tree Problem: Connect a subset of vertices at minimum cost, a fundamental problem in network design. - 🖧 Survivable Network Design: Design networks resilient to failures, ensuring connectivity under various scenarios. - 📡 Wireless Network Design: Design wireless networks with limited resources, optimizing coverage and capacity. --- count: false class: nord-dark, middle, center .pull-left[ # 🙋 Q & A ] .pull-right[  ]