CSCE 411 Lecture 7

Lecture Slides

« previous | Monday, September 10, 2012 | next »

Greedy Algorithms and Matroids

Useful for solving optimization problems

1. Cast optimization problem as one in which we make a choice and are left with one subproblem to solve
2. Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe
3. Demonstrate that, having made the greedy choice, what remains is a subproblem with the property that if we combine an optimal solution to the subproblem with the greedy choice that we have made, we arrive at an optimal solution to the original problem.

geedy-choice property: globally optimal solution that can be arrived at by making the optimal (hence greedy) choice at each step of the algorithm.

Easy to design, but hard to show correctness.

Giving Change

Suppose we have $n$ types of coins with values $v_{1}>v_{2}>v_{3}>\dots >v_{n}>0$.

Given an amount $C$, a positive integer, the following algorithm tries to give change for $C$:

num_coins = Array.new(n, 0)
(1..n).each do |i|
    while C >= v[i]
        C -= v[i]
        num_coins[i] += 1
    end
end

# C == (1..n).map{|i| num_coins[i]*v[i]}.inject(:+)

Is this solution optimal? Does it give the least number of coins?

Suppose $v=[5,2,1]$.

Optimal solution must satisfy

1. if $m_{3}\geq 2$, replace two 1's with a 2
2. $2m_{2}+m_{1}<5$, otherwise we would use a 5
3. If $C\geq 5*k$, then $m_{1}\geq k$ or solution would violate (2)

Q.E.D. The optimal solution is the greedy solution.

HOWEVER

If $v=[4,3,1]$, our algorithm would choose $6=4+1+1$, which is not optimal.

In order for greedy algorithms to work, the optimal solution to a larger problem must have an optimal solution to its subproblems. (optimal substructure )

Matroids

Combinatorial structure

Let $S$ be a finite set, and $F$ be a nonempty family of subsets of $S$, i.e. $F\subseteq {\mathcal {P}}(S)$

We call $(S,F)$ a matroid iff

1. $B\in F\wedge A\subseteq B\implies A\in F$ (hereditary)
2. $A,B\in F\wedge |A|<|B|\implies \exists x\in (B\setminus A):A\cup \{x\}\in F$ (exchange property)

Example 1: Matric Matroids

Let $M$ be a matrix Let $S$ be the set of rows of $M$ and $F=\{A\mid A\subseteq S,A{\mbox{ is linearly independent}}\}$

Claim: $(S,F)$ is a matroid.

$F$ isn't empty (it contains every row of $M$)

1. If $B$ is a set of linearly independent rows of $M$, then any subset $A$ of $M$ is linearly independent, so $F$ is hereditary.
2. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A,B} are sets of linearly independent rows of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} , then dim span Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} < dim span Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} . Choose a row Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} that is not contained in span Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \cup \{x\}} is a linearly independent subset of rows of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} satisfies the exchange property.

Graphs

A set of Vertices/nodes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} and Edges Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E \subseteq \{e \mid e \subset V \wedge |e| = 2 \}}

An induced graph is a graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (V,E')} that contains a subset of edges of an original graph Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (V, E)} .