COMS 482: unofficial class blog

Minimum Spanning Tree (MST):

Given a connected graph G=(V,E), a spanning tree is a connected subgraph on V. A minimal spanning tree is a spanning tree with the minimal number of edges.

“A spanning tree is a tree.”

To not be a tree, it must (a) be not connected or (b) have a cycle. By definition, (a) is false, because an MST is defined as a connected subgraph. For (b), if a cycle exists we can erase any edge in the cycle and still maintain connectedness.

Each edge has a cost. The minimum spanning tree is a least total cost tree. For example:

MST Algorithm:

• Choose all edges, dropping expensive edges until you have a complete tree
• Choose least cost edges that do not make a cycle (Kruskal’s)
• Build a single tree, always adding least cost edges (Prim’s)

Kruskal’s Algorithm:

Sort edges by cost
T = {}
for e in edges do
    if e does not create a cycle then
        add e to T
    endif
endfor

Prim’s Algorithm:

Choose a start vertex s
T = {s}
While there is a vertex not in T do
    choose least cost edge from T to some vertex not in T
    add this edge to T
endwhile

“Kruskal’s algorithm produces an MST”

Let k₁, … , k_n-1 be edges added by Kruskal’s algorithm in the order added. Assume k₁, … , k_n-1 is not an MST. Then let k_i be the first edge added that makes it impossible to extend k₁, … , k_i to an MST. Consider a true MST that uses k₁, … , k_i-1. Let k₁, … , k_i-1,m_i, …, m_n-1 be the true MST. If we add k_i to k₁, … , k_i-1,m_i, …, m_n-1 (true MST) then we get a cycle. This cycle contains some edge m_j where j >= i. The cycle cannot be all k’s because Kruskal’s algorithm would not have added k.

Consider the graph from adding k_i and removing m_j in k₁, … , k_i-1,m_i, …, m_n-1. We still have a spanning tree, with three cases:

1. |k_i| < |m_j| => Contradiction, because the new tree has less cost than the true MST
2. |k_i| > |m_j| => Contradiction, because m_j would have been chosen by Kruskal's algorithm before k_i.
3. |k_i| = |m_j| => Contradiction, because now both trees are MST and have the same cost, but k_i was chosen to not be in an MST with k₁, … , k_i.

I installed MS Visio on my computer, so now lecture notes will contain graphs where appropriate!

Homework 1 is online, on the website. Due Friday.

• The schedule is now online.
• HW1 is due on Friday
• If the bookstore is out of course packets, put in a request for one so that they’ll print more. Otherwise you might not get one.

(4.1 – 4.6) Greedy Algorithms:

• Always choose a local optimum
• Stable Marriage is an example of a greedy algorithm

Solving an algorithms problem:

1. Give an algorithm
2. Give a proof of correctness
3. Analyze running time

Interval Scheduling:

Some suggestions for choosing the interval segments. Choose the:

• First to finish
• x Shortest one
• x First left endpoint
• x One with fewest conflicts

S = {segments}
A = {}
while S != {} do
    choose s in S with minimum right endpoint
    A = A U {s}
    delete all s’ in S that overlap with s
end

“The r^th interval is at least as good as the r^th interval in the optimal set”

A contains no overlapping intervals. Let {i₁, … , i_k} be the set of segments added to A, in order, and let {j₁, … , j_k} be the set of segments in O, the optimal solution. Since by our rule f(i₁) < = f(j₁), we see that we "stay ahead" of the optimal solution at each step by choosing the "shortest" possible segment. This allows us to assume that f(i_r-1) < = f(j_r-1). We know that f(j_r-1) < = s(j_r) because all the segments in S are compatible. With our inductive assumption, we can write f(i_r-1) < = s(j_r), thus j_r has not been already selected or eliminated when we choose i_r. Since the greedy algorithm chooses the interval with the smallest finish time, we pick one equal or smaller to j_r: i_r < = j_r.

“A is an optimal solution”

By contradiction, if A isn’t optimal, then the optimal set O will have more requests. This would mean that (a) there must be m > k requests, and (b) O makes a k+1^th request after both i_k and j_k end. This means that after deleting all requests that are incompatible with {i₁, … , i_k} the set of possible requests R still contains j_k+1. But the greedy algorithm stops on request i_k, and it only stops when R is empty–a contradiction!

1) Interval Scheduling: Given a set of line segments on the x-axis, choose the largest possible (by count) subset that is non-overlapping. For example, this represents a solution to scheduling a heavily requested conference room, minimizing the number of parties who don’t get the room.

2) Weighted Interval Scheduling: The same as (1), but now each line segment carries a “points” weight. The goal is to maximize the total number of “points.” For example, you could assign more points to groups requesting conference room time who have high-ranking executives in the meeting.

• This is a harder problem than (1). A solution for Weighted Interval Scheduling degrades to Interval Scheduling when the weights are all one, but not vice verse

3) Independent Set: Given a graph G=(V, E), find the largest possible set of independent vertices, that is, the set of vertices not connected by an edge (example).

“Interval scheduling is a special case of Independent Set.”

Given a set S={s₁, … , s_n} of segments, create a vertex for each interval and connect two vertices if their intervals overlap:

4) Bipartite Matching: First, a definition. “Bipartite graph” means the vertex set is divided into 2 subsets V = X + Y such that X ^ Y = {}, i.e. there are only edges between the members of the two subsets. A perfect bipartite match would use all the vertices. Here, the goal is to find the largest possible matching. It is similar to the stable marriage problem.

“Bipartite matching is a special case of independent set.”

Convert a given bipartite matching problem (BPM) into an independent set (IS) problem by first creating an IS vertex for each edge in the BMP. Connect two vertices in the IS graph if their BPM edges share a vertex. Then select the largest Independent Set.

5) Competitive Facility Location: Given two restaurants, a weighted map of desirable block locations, and zoning laws that forbid adjacent shops, come up with a strategy to maximize your points in placing the restaurant locations turn by turn.

Summary:

• Competitive Facility Location (PSPACE Complete)
  • Independent Set (NP Complete)
    • Bipartite Matching (Network Flow)
    • Weighted Interval Scheduling (Dynamic Programming)
      • Interval Scheduling (Greedy)