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\ge 2$, replace two 1's with a 2
2. $2m_2+m_1<5$, otherwise we would use a 5
3. If $C\ge 5*k$, then $m_1\ge 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 {𝒫}(S)$

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

1. $B\in F\wedge A\subseteq B⟹A\in F$ (hereditary)
2. $A,B\in F\wedge |A|<|B|⟹\mathrm{\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\text{ 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 $A,B$ are sets of linearly independent rows of $M$, then dim span $A$ < dim span $B$. Choose a row $x$ in $B$ that is not contained in span $A$. Then $A\cup \{x\}$ is a linearly independent subset of rows of $M$, so $F$ satisfies the exchange property.

Graphs

A set of Vertices/nodes $V$ and Edges $E\subseteq \{e\mid e\subset V\wedge |e|=2\}$

An induced graph is a graph $(V,E^{\prime })$ that contains a subset of edges of an original graph $(V,E)$.