Introduction to Combinatorial Optimization

---

# 🧩 Introduction to Combinatorial Optimization

**Approximation Classes** 🏆

### Finding the Best Structure Among Finite Possibilities

@luk036 👨‍💻 · 2026 📅

---

### 📋 Agenda

**🎯 Motivation & Problem Classes**
- Approximation Classes 🏆
- What is Combinatorial Optimization?
- Classic Problems: P to NP-hard

**🌐 Part 1: Networks & Fundamentals**
- Networks Are Everywhere
- Shortest Path & NCF ➖
- Flow & Potential Duality ⚖️

**🔄 Part 2: Core Algorithms**
- Min-Cost Flow 💰
- Max-Flow & Min-Cut ✂️
- Parametric Problems 📈

]
.pull-right[

**☯ Part 3: Primal-Dual & Feasibility**
- Primal-Dual Framework
- Weighted Vertex Cover
- Feasibility Theorems

**🛠️ Part 4: Applications & Tools**
- Clock Skew · Matrix Scaling
- Performance Analysis
- Tools & Libraries 📦

**🎯 Part 5: Wrap-Up**
- Key Takeaways
- Q&A · References

]

---

### 🏆 Approximation Classes

**Not all computationally hard problems are equally hard.** Some admit good approximations, others don't.

.mermaid[
<pre>
graph TD
    NPHD["NPO-hard\n❌ No constant-factor\napproximation possible"] -->|"hardest"| APX["APX-hard\n⚠️ Approximable within\nsome constant factor"]
    APX -->|"hard"| PTAS["PTAS\n✅ (1+ε)-approximation\nfor any ε > 0"]
    PTAS -->|"easier"| FPTAS["FPTAS\n✅ Polynomial in both\ninput size and 1/ε"]
    FPTAS -->|"easiest"| P["P\n✅ Exact solution\nin polynomial time"]
    style NPHD fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style APX fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style PTAS fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style FPTAS fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style P fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
</pre>
]

**The good news**: Network optimization problems — shortest path, max-flow, min-cost flow — are in **P**. They form a rare "island of tractability" in a sea of NP-hardness. 🏝️

---

### 🤔 What is Combinatorial Optimization?

**Definition**: Optimizing a function over a **finite but huge** discrete set of feasible solutions.

.pull-left[
**Key Characteristics** 📋
- Decision variables are **discrete**: binary, integer, permutation
- Search space is **finite** but astronomically large — $O(N!)$, $O(2^N)$
- Brute force is **impossible** for practical instances 🔍
- Need **clever algorithms** that exploit mathematical structure
- Some problems are easy (P), some are hard (NP-hard)
]
.pull-right[
**Three Questions** 🤔
1. **Feasibility**: Does a solution exist? ✅
2. **Optimality**: What is the best solution? 💯
3. **Approximation**: How close can we get to optimal? 🎯

> "Combinatorial optimization is the art of finding the best solution without enumerating all possibilities." 🎨
]

---

### 🎯 Classic Problems: The Spectrum

From easy to hard — every problem has its place:

| Problem | Complexity | Best Known |
|---------|:---:|-------------|
| Shortest Path 🛣️ | P | Bellman-Ford, Dijkstra |
| Minimum Spanning Tree 🌳 | P | Kruskal, Prim (greedy) |
| Max-Flow / Min-Cut ✂️ | P | Ford-Fulkerson, Push-Relabel |
| Min-Cost Flow 💰 | P | Cycle canceling, network simplex |
| **Minimum Vertex Cover** 🛡️ | APX-C | 2-approximation (PD) |
| **Metric TSP** 🗺️ | APX-C | 3/2-approximation (Christofides) |
| **Steiner Tree** 🌿 | APX-C | ≈1.39-approximation |
| General TSP 🗺️ | NPO-C | Not approximable |
| SAT (Boolean satisfiability) 🔤 | NP-C | Not approximable |

**Key insight**: Network structure (graphs, flows, cycles) makes problems **tractable** — it constrains the search space enough for efficient algorithms.

---

## Part 1: Networks & Fundamentals 🌐

---

### 🌐 Networks Are Everywhere

Many combinatorial optimization problems are naturally expressed as **networks** (directed/undirected graphs with edge weights):

.pull-left[
**Ubiquitous Networks** 📍
- **Circuit** 🔌 — VLSI routing, timing analysis
- **Internet** 🌍 — Routing, flow control, web graphs
- **Social Network** 👥 — Influence, communities
- **Neural Network** 🧠 — Deep learning architectures
- **Transportation** 🚗 — GPS, airlines, logistics
- **Biology** 🧬 — Metabolic networks, protein interactions
]
.pull-right[
.mermaid[
<pre>
graph TD
    subgraph Networks["Network Types"]
        A1["Circuit\nVLSI"] --- A2["Internet\nWeb"]
        A2 --- A3["Social\nNetworks"]
        A3 --- A4["Neural\nNetworks"]
        A4 --- A1
    end
    B["Combinatorial\nOptimization"] --> Networks
    style Networks fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style B fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style A1 fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
    style A2 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style A3 fill:#fff3e0,stroke:#e65100,stroke-width:3px
    style A4 fill:#f3e5f5,stroke:#7b1fa2,stroke-width:3px
</pre>
]
]

**Why networks help**: They combine **numeric** (edge weights) and **discrete** (topology) aspects. The structure — cycles, cuts, duality — yields efficient algorithms. 🔑

---

### 🛣️ Shortest Path Problem

**Problem**: Find the minimum-weight path between two nodes in a directed graph.

$$ \min_{{\color{lime}P} \in \mathcal{P}_{st}} \sum_{e \in {\color{lime}P}} {\color{coral}w}(e) $$

.pull-left[
**Bellman-Ford Algorithm** ⏱️
- $O(V \cdot E)$ — polynomial time!
- Handles **negative edge weights**
- Detects **negative cycles** as a side effect
- Dynamic programming: relax edges repeatedly

$$
{\color{firebrick}\text{dist}}[v] = \min({\color{firebrick}\text{dist}}[v],\; {\color{firebrick}\text{dist}}[u] + {\color{coral}w}(u,v))
$$
]
.pull-right[
.mermaid[
<pre>
graph LR
    A[("s")] -->|"3"| B[("a")]
    A -->|"5"| C[("b")]
    B -->|"2"| D[("c")]
    C -->|"1"| D
    D -->|"4"| E[("t")]
    B -->|"-1"| E
    style A fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style E fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style B fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style C fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style D fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px
</pre>
]

**Polynomial time** ✅ — no need to enumerate all paths! The graph structure prunes the search. 🔑
]

---

### ➖ Negative Cycle Finding (NCF)

**Definition**: A **negative cycle** is a directed cycle whose edge weights sum to a negative number:

$$ \sum_{(i,j) \in {\color{lime}C}} {\color{coral}w}(i,j) < 0 $$

1. **Shortest paths**: a negative cycle → no finite shortest path exists
2. **Feasibility**: ${\color{firebrick}u}_j - {\color{firebrick}u}_i \le {\color{coral}w}(i,j)$ has no solution ⇔ a negative cycle
3. **Optimality**: in min-cost flow, negative cycles = improvement directions
4. **Cutting-plane oracles**: each negative cycle yields a cut
5. **Parametric search**: ratio problems reduce to NCF
]
.pull-right[
.mermaid[
<pre>
graph TD
    NCF["Negative Cycle\nFinder (NCF)"] --> SP["Shortest\nPath"]
    NCF --> FEAS["Feasibility\nCheck"]
    NCF --> OPT["Optimality\n(Cycle Cancel)"]
    NCF --> CUT["Cutting Plane\nGeneration"]
    NCF --> PARAM["Parametric\nSearch"]
    style NCF fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style SP fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style FEAS fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style OPT fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style CUT fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px
    style PARAM fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
</pre>
]

**Howard's algorithm** 🏆: policy iteration, no source node required, generator-based — powers the entire ecosystem.
]

---

### ⚖️ Flow and Potential Duality

Networks exhibit a beautiful duality between **flow** (edge quantities) and **potential** (node quantities):

$$ \text{div}\, {\color{green}x} = {\color{blue} A^\mathsf{T} } {\color{green}x} = 0 $$

- ${\color{green}x}$: flow on each edge
- ${\color{blue}A}$: node-edge incidence matrix
- Flow **conserved** at every internal node
- **Cut** ✂️: set of edges across a bipartition of nodes
]
.pull-right[
**Potential** ⚡ (Kirchhoff's Voltage Law)

$$ {\color{blue}y} = {\color{green} A} {\color{firebrick}u} $$

- ${\color{firebrick}u}$: potential at each node
- ${\color{blue}y}$: tension = potential difference
- Tension sums to **zero around any cycle**
- **Cycle** 🔄: closed path in the graph
]

**Tellegen's Theorem**: ${\color{green}x}^\mathsf{T} {\color{blue}y} = 0$ — flow and tension are always orthogonal. This is the foundation of **complementary slackness**. 🔑

---

### 📐 Network Algebra

The **incidence matrix** ${\color{blue}A}$ encodes the entire network structure:

$$ {\color{blue} A}(i,j) =
\begin{cases}
+1 & \text{if edge ${\color{darkgreen}e_j}$ leaves node ${\color{brown}v_i}$}, \\
-1 & \text{if edge ${\color{darkgreen}e_j}$ enters node ${\color{brown}v_i}$}, \\
0 & \text{otherwise}.
\end{cases} $$

| Operator | Defn | Maps |
|----------|------|------|
| Boundary | ${\color{blue}\partial} = {\color{blue}A^\mathsf{T}}$ | edge → node |
| Coboundary | ${\color{green}\mathrm{d}} = {\color{green}A}$ | node → edge |
| Divergence | $\text{div}\, {\color{green}x} = {\color{blue}A^\mathsf{T}} {\color{green}x}$ | edge → node |
| Tension | ${\color{blue}y} = {\color{green}A} {\color{firebrick}u}$ | node → edge |
]
.pull-right[
**Fundamental Theorems** 📜

- **Discrete Stokes**: ${\color{purple}[}{\color{blue}A^\mathsf{T}} {\color{green}\tau}, {\color{firebrick}u}{\color{purple}]} = {\color{purple}[}{\color{green}\tau}, {\color{green}A} {\color{firebrick}u}{\color{purple}]}$
- **Cycle**: ${\color{blue}A^\mathsf{T}} {\color{green}\tau} = 0$ (nullspace of boundary)
- **Cut**: ${\color{blue}q} = {\color{green}A} {\color{firebrick}c}$ (range of coboundary)
- **Rank**: $\dim(\ker {\color{blue}A^\mathsf{T}}) = M - N + c$
  ($c$ = # components)

> All of network optimization can be expressed in this algebraic language. 🧮
]

---

## Part 2: Core Algorithms 🔄

---

### 💰 Minimum Cost Flow Problem (MCFP)

**Formulation**: Find a flow ${\color{green}x}$ minimizing total cost:

$$
\begin{array}{ll}
\text{min} & {\color{blue}d}^\mathsf{T} {\color{green}x} \\
\text{s.t.} & 0 \le {\color{green}x} \le {\color{green}c}, \\
& {\color{blue} A^\mathsf{T} }{\color{green}x} = {\color{firebrick}b},\; {\color{firebrick}b}({\color{salmon}V}) = 0
\end{array}
$$

**Descent Method**: From feasible ${\color{green}x}_0$, find better ${\color{green}x}_1 = {\color{green}x}_0 + \alpha \cdot p$:

- Cost must decrease: ${\color{blue}d}^\mathsf{T} p < 0$ 📉
- Feasibility preserved: ${\color{blue}A^\mathsf{T}} p = 0$ ⇒ **$p$ must be a cycle**! 🔄

.mermaid[
<pre>
graph LR
    X0["Initial flow x₀"] -->|"Find negative\ncycle p"| NCF["NCF Engine"]
    NCF -->|"p found"| UPDATE["x ← x + α·p\n(improvement)"]
    UPDATE -->|"iterate"| NCF
    NCF -->|"no cycles"| OPTIMAL["Optimal! ✅"]
    style X0 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style NCF fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style UPDATE fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px
    style OPTIMAL fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
</pre>
]

**This is the cycle-canceling algorithm** — and it works because the NCF primitive is so powerful! 🔑

---

### ✂️ Max-Flow & Min-Cut

**Max-Flow Problem**: Route the maximum possible flow from source $s$ to sink $t$ through a capacitated network.

**Min-Cut Theorem** (Ford & Fulkerson): $\text{max-flow} = \text{min-cut}$ — one of the most celebrated results in combinatorial optimization! 🎯

.pull-left[
**Ford-Fulkerson** 🔧
```python
while there exists augmenting path:
    push flow along path
```
- $O(E \cdot f)$ for integer capacities
- **Edmonds-Karp** (BFS): $O(V \cdot E^2)$
- **Push-Relabel**: $O(V^3)$
]
.pull-right[
.mermaid[
<pre>
graph LR
    S[("s")] -->|"12"| A[("a")]
    S -->|"10"| B[("b")]
    A -->|"5"| B
    A -->|"8"| T[("t")]
    B -->|"15"| T
    style S fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style T fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style A fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style B fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
</pre>
]

Min-cut = ${\color{salmon}\{s\}}$ → capacity 22 = max-flow
]

**Applications**: Bipartite matching, image segmentation, network reliability, circuit partitioning, sports elimination. 🏀

---

### 📈 Parametric Problems

**Minimum Cycle Ratio (MCR)**: Find cycle ${\color{lime}C}$ with minimum cost-to-time ratio:

$$ \text{ratio}({\color{lime}C}) = \frac{\sum_{e \in {\color{lime}C}} {\color{coral}c}(e)}{\sum_{e \in {\color{lime}C}} {\color{coral}t}(e)} $$

**Parametric Reduction** 🔎: For a candidate ratio $r$, define adjusted weights:

$$ {\color{coral}w}_r(e) = {\color{coral}c}(e) - {\color{coral}r} \cdot {\color{coral}t}(e) $$

- If a **negative cycle** exists with ${\color{coral}w}_r$ → ${\color{coral}r}$ is **too high** (infeasible) 🔴
- If **no negative cycle** → ${\color{coral}r}$ is **feasible** 🟢

.mermaid[
<pre>
graph LR
    R0["Guess r₀"] --> W["Compute\nwᵣ(e) = c(e) - r·t(e)"]
    W --> NCF{"NCF: Negative\nCycle?"}
    NCF -->|"Yes → r too high"| DEC["Decrease r"]
    NCF -->|"No → r feasible"| INC["Increase r"]
    DEC --> W
    INC --> W
    style R0 fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px
    style W fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style NCF fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style DEC fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style INC fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
</pre>
]

**The NCF engine works here too!** Binary search or Howard iteration finds the optimal ${\color{coral}r}^*$. 🔑

---

### 🔎 Parametric Search — Full Flow

.mermaid[
<pre>
graph TD
    START["Start: initial r₀,\ndist = 0"] --> RELAX["Edge Relaxation\nupdate dist along edges"]
    RELAX --> CYCLE{"Find cycle in\npredecessor graph?"}
    CYCLE -->|"Yes"| VERIFY{"New ratio\nbetter than r?"}
    VERIFY -->|"Yes"| UPDATE["r ← ratio(C)\nUpdate dist along C"]
    VERIFY -->|"No"| RELAX
    CYCLE -->|"No"| DONE["Done! r* is optimal 🎯"]
    UPDATE --> RELAX
    style START fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style RELAX fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style CYCLE fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px
    style VERIFY fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style UPDATE fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style DONE fill:#eceff1,stroke:#455a64,color:#2e3440,stroke-width:3px
</pre>
]

**One primitive, many problems**: The same NCF engine powers shortest paths, feasibility checks, cycle canceling for MCFP, ratio optimization, and cutting-plane oracles — it's the Swiss Army knife of network optimization! 🇨🇭

---

## Part 3: Primal-Dual & Feasibility ☯

---

### 🧮 Primal-Dual Fundamentals

The **primal-dual method** designs approximation algorithms via LP duality — one of the most versatile frameworks in combinatorial optimization.

**Core Idea** 💡:
1. Formulate as **Integer Linear Program (ILP)** 📝
2. Relax to **LP**, then work with the **dual** ⚖️
3. Iteratively improve the dual solution while constructing a primal feasible solution 🔁
4. **Relax complementary slackness** → provable approximation guarantees

.pull-left[
**Why it matters** 🎯
- **Provable** approximation ratios
- Often yields **combinatorial** algorithms (no LP solver needed!)
- Reveals deep **problem structure**
- Works for: Vertex Cover, Steiner Tree, Set Cover, Survivable Networks
]
.pull-right[
**The PD-Approximation Principle** 📐

$$ \text{cost}(\text{primal}) \le \alpha \cdot \text{cost}(\text{dual}) \le \alpha \cdot \text{OPT} $$

The dual provides a **lower bound on OPT**. The primal is at most $\alpha$ times the dual → $\alpha$-approximation! ✅
]

---

### 📚 Primal-Dual Example: Weighted Vertex Cover

**Problem**: Given $G = ({\color{salmon}V}, {\color{lime}E})$ with vertex weights ${\color{coral}w}_v \ge 0$, find min-weight vertex subset covering all edges.

**ILP** → **LP Relaxation** → **Dual**:

.pull-left[
**Primal LP**:
$$
\begin{array}{lll}
\text{min} & \displaystyle\sum_{v} {\color{coral}w}_v {\color{green}x}_v \\
\text{s.t.} & {\color{green}x}_u + {\color{green}x}_v \ge 1, & \forall uv \in {\color{lime}E} \\
& 0 \le {\color{green}x}_v \le 1
\end{array}
$$
]
.pull-right[
**Dual LP**:
$$
\begin{array}{lll}
\text{max} & \displaystyle\sum_{e \in {\color{lime}E}} {\color{firebrick}y}_e \\
\text{s.t.} & \displaystyle\sum_{e \ni v} {\color{firebrick}y}_e \le {\color{coral}w}_v, & \forall v \in {\color{salmon}V} \\
& {\color{firebrick}y}_e \ge 0
\end{array}
$$
]

**Interpretation**: Each edge $e$ has a budget ${\color{firebrick}y}_e$. As we increase ${\color{firebrick}y}_e$, when $\sum_{e \ni v} {\color{firebrick}y}_e$ hits ${\color{coral}w}_v$, vertex $v$ "pays for itself" and gets added to the cover. 💡

---

### ⚙️ Primal-Dual Algorithm for WVC

```python
def min_vertex_cover(ugraph, weight, coverset=None):
    if coverset is None:
        coverset = set()
    gap = dict(weight)  # remaining slack per vertex

for u, v in ugraph.edges():
        if u in coverset or v in coverset:
            continue
        # Pick vertex with tighter constraint (smaller gap)
        if gap[u] < gap[v]:
            u, v = v, u
        coverset.add(v)
        gap[u] -= gap[v]  # transfer dual value
        gap[v] = 0
    return coverset
```

**How it works** 🔍:
- `gap[v]` = remaining slack before constraint $\sum_{e \ni v} {\color{firebrick}y}_e \le {\color{coral}w}_v$ becomes tight
- For each uncovered edge, add the vertex with **smaller gap** (it will bind first)
- Transfer the dual value to the other vertex (Bookkeeping via gap reduction)

**Result**: 2-approximation — the cover cost $\le 2 \cdot \text{OPT}$. Guaranteed and simple! ✅

---

### 🔄 Generic Primal-Dual for Cover Problems

The WVC pattern generalizes to many covering problems:

```python
def pd_cover(violate, weight, soln):
    """Generic primal-dual covering algorithm."""
    total_dual = 0
    total_prml = 0
    gap = dict(weight)

for S in violate():         # Each S is a violated constraint set
        min_vtx = min(S, key=lambda v: gap[v])
        min_val = gap[min_vtx]

soln.add(min_vtx)        # Add to our solution
        total_prml += weight[min_vtx]
        total_dual += min_val

for v in S:              # Reduce gaps across the set
            gap[v] -= min_val

assert total_dual <= total_prml
    return soln, total_prml
```

**The `violate()` generator** yields violated constraint sets:
- Uncovered edges → **Vertex Cover** 🛡️
- Found cycles → **Cycle Cover** 🔄
- Odd-length cycles → **Odd Cycle Cover** 🟣
- Uncovered hyperedges → **Hypergraph Cover** 🔗
- Steiner components → **Steiner Tree** 🌿

---

### 🔄 Primal-Dual — Flow Diagram

.mermaid[
<pre>
graph TD
    A(("Problem\nInstance")) --> B("ILP Formulation\n📝")
    B --> C("LP Relaxation + Dual\n⚖️")
    C --> D{"Iterative\nTightening"}
    D -->|"Increase dual yₑ\nuntil tight"| E("Add tight vertex\nor edge ➕")
    D -->|"Update\ngaps"| F("Reduce gaps\nfor all in set")
    E --> G{"All constraints\nsatisfied?"}
    F --> G
    G -->|"No"| D
    G -->|"Yes"| H("Prune unnecessary\nelements ✂️")
    H --> I("α-Approximate\nSolution ✅")
    C -.->|"Dual solution"| J("Lower bound\non OPT 📊")
    J -.-> I
    style A fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style B fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style C fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px
    style D fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style E fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style F fill:#e0f7fa,stroke:#00838f,color:#2e3440,stroke-width:3px
    style G fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style H fill:#efebe9,stroke:#4e342e,color:#2e3440,stroke-width:3px
    style I fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style J fill:#eceff1,stroke:#455a64,color:#2e3440,stroke-width:3px
</pre>
]

**Connection to network optimization**: The cycle-canceling algorithm for MCFP is itself a primal-dual method — the negative cycle is the "violated constraint" that guides improvement. 🔄

---

### ✅ Feasible Flow Problem

**Question**: Does there exist a flow ${\color{green}x}$ satisfying capacity and supply/demand?

$$
\begin{array}{ll}
{\color{green}c^-} \le {\color{green}x} \le {\color{green}c^+}, \\
{\color{blue} A^\mathsf{T} }{\color{green}x} = {\color{firebrick}b},\; {\color{firebrick}b}({\color{salmon}V}) = 0
\end{array}
$$

**Theorem** 📜: A feasible flow exists **iff** for every cut $Q = [S, S']$:

$$ {\color{firebrick}b}(S) \le {\color{green}c^+}(Q) $$

**Interpretation**: Supply inside any region cannot exceed the capacity of edges leaving it.

**Algorithm**: **Painted network algorithm** — returns a **negative cut** ✂️ if infeasible.

---

### ⚡ Feasible Potential Problem

**Question**: Does there exist a potential ${\color{firebrick}u}$ satisfying tension bounds?

$$
\begin{array}{ll}
{\color{blue}d^-} \le {\color{blue}y} \le {\color{blue}d^+}, \\
{\color{green}A} \cdot {\color{firebrick}u} = {\color{blue}y}
\end{array}
$$

**Theorem** 📜: A feasible potential exists **iff** for every cycle $P$:

$$ {\color{blue}d^+}(P) \ge 0 $$

.pull-left[
**Primal (Flow)** 💧
- Cut-based feasibility
- Painted network algorithm
- Returns negative cut ✂️
]
.pull-right[
**Dual (Potential)** ⚡
- Cycle-based feasibility
- Bellman-Ford algorithm
- Returns negative cycle ➖
]

**Duality in action**: Flow and potential are dual problems — solving one solves the other. The feasibility of one is equivalent to the non-existence of a "negative" structure in the other. ☯

---

## Part 4: Applications & Tools 🛠️

---

### ⏰ Application: Clock Skew Scheduling

In VLSI design, **clock skew** ${\color{blue}s}_{ij} = {\color{firebrick}u}_i - {\color{firebrick}u}_j$ is the difference in clock arrival times between registers:

$$
\begin{array}{ll}
{\color{firebrick}u}_j - {\color{firebrick}u}_i \le T_{\text{clk}} - D_{\max}(i,j) & \text{(setup)} \\[4pt]
{\color{firebrick}u}_i - {\color{firebrick}u}_j \le D_{\min}(i,j) - T_{\text{hold}} & \text{(hold)}
\end{array}
$$

.mermaid[
<pre>
graph LR
    FF1["FF₁\narrival u₁"] -->|"D_max, D_min"| FF2["FF₂\narrival u₂"]
    C1["u₂ - u₁ ≤ T_clk - D_max\nu₁ - u₂ ≤ D_min - T_hold"]
    FF1 --> C1
    FF2 --> C1
    style FF1 fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style FF2 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style C1 fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
</pre>
]

This is a **difference constraints system** — a special case of the Feasible Potential Problem! A negative cycle means timing cannot be closed. All solvable by NCF. 🚫

---

### ✨ Application: Optimal Matrix Scaling

**Problem** (Orlin & Rothblum, 1985): Given matrix ${\color{green}A} = ({\color{coral}a}_{ij})$, find diagonal scaling ${\color{firebrick}u}_i > 0$ that minimizes the ratio spread:

$$ \min \frac{{\color{coral}\pi}}{{\color{coral}\psi}} \quad\text{s.t.}\quad {\color{coral}\psi} \le {\color{firebrick}u}_i \cdot |{\color{coral}a}_{ij}| \cdot {\color{firebrick}u}_j^{-1} \le {\color{coral}\pi},\; \forall {\color{coral}a}_{ij} \ne 0 $$

**Reduction**: Take logs: ${\color{green}x} = (\log{\color{coral}\pi},\; \log{\color{coral}\psi})$, ${\color{coral}\text{cost}} = \log|{\color{coral}a}_{ij}|$. The constraint becomes:

$$ \min({\color{green}x}_0 - {\color{coral}\text{cost}}_{ji},\; {\color{coral}\text{cost}}_{ij} - {\color{green}x}_1) \ge 0 $$

- Build graph from matrix sparsity
- Use cutting-plane + NCF oracle
- Ellipsoid method for 2-parameter optimization
]
.pull-right[
**Applications** 📍
- **Preconditioning**: Numerical stability
- **Economic equilibrium**: Exchange rates
- **Chemical engineering**: Reaction rates
- **Traffic networks**: OD matrix balancing
]

---

### 📊 Application: Performance Analysis

**Minimum Cycle Ratio** determines the maximum clock frequency:

$$ F_{\max} = \frac{1}{\text{MCR}},\quad {\color{coral}r}^* = \max_{{\color{lime}C}} \frac{\sum \text{gate delays}}{\sum \text{registers}} $$

.pull-left[
.mermaid[
<pre>
graph LR
    A["R₁"] -->|"2ns"| B["R₂"]
    B -->|"3ns"| C["R₃"]
    C -->|"1ns"| D["R₄"]
    D -->|"2ns"| A
    B -->|"1ns"| D
    style A fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style B fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style C fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style D fill:#fff9c4,stroke:#f57f17,color:#2e3440,stroke-width:3px
</pre>
]

R₁→R₂→R₃→R₄→R₁: ratio = (2+3+1+2)/4 = **2.0 ns** → **500 MHz** 🔴
]
.pull-right[
**Why it matters** 🎯:
- The **critical cycle** is the performance bottleneck
- MCR identifies it **automatically**
- No need to manually trace paths
- Works for any circuit graph

**Other applications**:
- 🕒 Optimal clock period
- ⏳ Slack maximization
- 🎲 Yield-driven scheduling
]

---

### 🛠️ Tools & Libraries

| Tool | Purpose |
|------|---------|
| **digraphx** | NCF, MCR, parametric search |
| **networkx** | General graph algorithms |
| **netlistx** | PD covering algorithms |
| **ellalgo** | Ellipsoid method, cutting-plane |

**C++** ⚡

| Tool | Purpose |
|------|---------|
| **digraphx-cpp** | Howard's NCF (CSR, fast) |
| **netoptim-cpp** | Network oracles |
| **LEMON** | Graph algorithms library |
| **BGL** | Boost Graph Library |
]
.pull-right[
.mermaid[
<pre>
graph TD
    subgraph Ecosystem["Network Optimization Ecosystem"]
        P1["digraphx\n(Python NCF/MCR)"] --> P2["netoptim-cpp\n(C++ Oracles)"]
        P2 --> P3["digraphx-cpp\n(C++ NCF Engine)"]
        P3 --> P4["ellalgo-cpp\n(Cutting-Plane)"]
        P1 --> P5["networkx\n(Python Graphs)"]
        P3 --> P6["LEMON\n(C++ Graphs)"]
        P2 --> P7["netlistx\n(PD Covering)"]
    end
    style Ecosystem fill:#e3f2fd,stroke:#1565c0,stroke-width:3px
    style P1 fill:#e3f2fd,stroke:#1565c0,color:#2e3440,stroke-width:3px
    style P2 fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style P3 fill:#fff3e0,stroke:#e65100,color:#2e3440,stroke-width:3px
    style P4 fill:#f3e5f5,stroke:#7b1fa2,color:#2e3440,stroke-width:3px
    style P5 fill:#c8e6c9,stroke:#2e7d32,color:#2e3440,stroke-width:3px
    style P6 fill:#ffcdd2,stroke:#c62828,color:#2e3440,stroke-width:3px
    style P7 fill:#e0f7fa,stroke:#00838f,color:#2e3440,stroke-width:3px
</pre>
]
]

---

### 📦 The `digraphx` Package

Lightweight Python package for directed graph optimization:

```python
from digraphx import NegCycleFinder, min_cycle_ratio

# Negative Cycle Detection
graph = {
    'A': [('B', -1), ('C', 4)],
    'B': [('C', 2), ('D', 2)],
    'C': [('D', -3)],
    'D': [('A', 1)]
}
finder = NegCycleFinder(graph)
for cycle in finder.howard():
    print(f"Negative cycle: {cycle}")
    # → Cycle with total weight < 0

# Minimum Cycle Ratio
ratio, cycle = min_cycle_ratio(
    graph,
    get_cost=lambda e: e['cost'],
    get_time=lambda e: e['time']
)
```

**Features**: ✅ Howard's algorithm ✅ Generator-based enumeration ✅ Warm-start support ✅ C++ backend available

---

## Part 5: Wrap-Up 🎯

---

### 🎯 Key Takeaways

1. 🏆 **Approximation classes** frame the difficulty: some problems are easy (P), some are approximable (APX/PTAS), some are hopeless (NPO). Knowing where your problem falls guides algorithm choice.

2. 🌐 **Network structure makes problems tractable** — shortest path, max-flow, min-cost flow are all in P. The graph constrains the search space enough for efficient algorithms.

3. ➖ **Negative cycle finding (NCF)** is the **universal primitive** — it powers shortest paths, feasibility detection, optimality (cycle canceling), ratio optimization, and cutting-plane generation.

4. ☯ **Primal-dual method** provides provable approximation guarantees (e.g., 2-approx for Vertex Cover) via a simple iterative tightening framework — no LP solver needed.

5. 📈 **Parametric search** reduces ratio optimization (MCR, max frequency) to repeated NCF feasibility checks — elegantly solving complex problems with a simple primitive.

6. 🔄 **Everything is connected**: flow ⟷ potential, cut ⟷ cycle, primal ⟷ dual. Each concept illuminates the others.

> "All models are wrong, but some are useful." — George Box. Network optimization is one of the most useful. 🌊

---

# 🙋 Q&A

### Questions? Discussion?

---

# 👏 Thank You

### References 📚

- Howard (1960) — Dynamic Programming and Markov Processes
- Karp (1967) — Minimum Mean Cycle Algorithm
- Orlin & Rothblum (1985) — Optimal Matrix Scaling
- Ford & Fulkerson (1956) — Max Flow Algorithm
- Bar-Yehuda & Even (1981) — Primal-Dual Vertex Cover

### Explore More 🔍

- **digraphx**: [github.com/luk036/digraphx](https://github.com/luk036/digraphx)
- **netlistx**: Primal-dual covering algorithms
- **netoptim-cpp**: C++ network optimization oracles

Slides built with Remark.js 🎉 | KaTeX | Mermaid | Nord Theme