LEC ALGO 9

Greedy algorithms

For a greedy approach to be viable, the problem must have

• optimal substructure, that is, a solution of a subproblem is contained in the solution of the parent problem.
• the greedy choice property: a globally optimal solution can be arrived at by locally optimal choices.

[!Example] Minimum spanning tree
Recall Kruskal’s algorithm for MSTs.

Optimal substructure: Let $T$ be a MST of $G$, and $e\in T$. If $T^{\prime }$ is a MST of $G\setminus e$, then $T_e=T^{\prime }\cup \{e\}$ is a MST of $G$.

Proof: Let $T^{\ast }$ be a MST of $G$ that contains $e$. $T^{\ast }\setminus e$ is a spanning tree of $G^{\prime }$. $W(T^{\prime })\le W(T^{\ast }\setminus e)=W(T^{\ast })-W(e)$. Thus, $W(T_e)=W(T^{{}^{\prime }})+W(e)\le W(T^{\ast })$.

This gives us a generic algorithm:

1. Find select a “safe edge” $e$.
2. Contract the edge $e$.
3. Recurse on $G\setminus e$.
4. Expand and add $e$.

Greedy choice property: Given any $S\subseteq V$, $(V,S\setminus V)$ is a cut of $G$.

Claim: For any cut $(S,V\setminus S)$ in a graph $G=(V,E,W)$ any least weight crossing edge is in some spanning tree.

Prim’s algorithm