CS330 HW07

Problem 1 §

Algorithm §

# each item is in format (time, start/end, event_index)
# order priosity: smaller time -> start ->
Q = sort(L, R)
Events = []

while Q has elements:

	if Q.next is a start time
		t <- Q.dequeue

		# if there is a tie in start times
		while Q.next.start_time == t.start_time:
			t <- max_end_time(t, Q.dequeue)
			
		# t is now the earliest starting time with maximum duration
	
	else Q.next is an end time

		# get latest end time
		while Q.next is an end time
			t <- Q.dequeue
			
		# t is now the latest end time
		
	add t's event to Events
	
	end if
end while

Complexity §

• Sorting: $O(n\log n)$
• Loop: $O(n)$
• ⇒ Total: $O(n\log n)$

Correctness §

• Base case
  1. Let $Y^{\ast }=(y_1,\dots )$ the optimal solution
  2. Assume $Y^{\ast }$’s $y_1$ is not the earliest start time……(1)
  3. Algorithm chooses earliest start time $x_1$.
     1. $[x_1.\text{start},y_1.\text{start}]$ is in total cover, but not in $Y^{\ast }$’s cover.
     2. This means $Y^{\ast }$ cannot be optimal. This is a contradiciton
     3. Thus Assumption (1) must be wrong
• Inductive Step
  1. Let $Y^{\ast }=(x_1\dots x_{k-1},y_k,\dots )$ is the optimal solution
  2. $Y^{\ast }$’s $y_k$ is the optimal next choice after $x_{k-1}$
  3. Case 1: next item in priority queue is an end time
     1. Algorithm chooses $x_k$ where…
        1. $x_k.\text{start}<x_{k-1}.\text{end}$
        2. $x_k.\text{end}<y_{k+1}.\text{start}$
        3. among such points, $\text{max}(x_k.end)$
     2. Assume $y_k$ is an event that doesn’t satisfy the maximum endtime requirement……(2)
        1. Then, $[y_k.\text{end},x_k.\text{end}]$ is in total cover, but not in $Y^{\ast }$’s cover. This is a contradiction.
        2. Thus assumption (2) must be wrong
  4. Case 2: next item in priority queue is a start time
     1. Algorithm chooses $x_k$ with the earliest starting time and longest duration
     2. This is at least as optimal as $y_k$, because…
        1. $x_k.\text{start}\le y_k.\text{start}$
        2. $x_k.\text{end}\le y_k.\text{end}$
        3. Thus the cover of $x_k$ is as large as $y_k$
     3. Thus $x_k$ is as optimal as $y_k$
• QED

Problem 2 §

// Idea: Reverse the order of weights in the graph,
// then run minimum spanning tree.

// First, reverse the weight ordering of the graph

// negate weights...
for e in E
	e' <- e
	e'.weight <- -e.weight
	add e' to E'

let m be the edge with minimum weight in E'

// then monotonically increase so all weights are positive 
// (to use MST algorithm)
for e in E'
	e'.weight += m.weight + 1

// Then, run MST algorithm (Prim or Kruskal)
V_mst, E_mst <- MST(V, E')

// the minimum spanning tree in (V, E') is
// same as the maximum spanning tree in (V, E)

// Return the edges that are not in the MST.
return E \ E_mst

Correctness §

• The problem is equivalent to getting a tree whose sum of edge weights is maximal.
  • This is because the remaining graph must be acyclic (a tree) and…
  • …because the sum of removed weights is minimal thus the sum of remaining weights must be maximal.
• We can convert the original graph in question to a weight order reversed graph:
  • Suppose $E=\{e_1,e_2,\dots ,e_m\}$ where $e_i$ has weight $w_i$
  • Then, $E^{\prime }=\{e_1^{\prime },\dots e_m^{\prime }\}$ where $e_i^{\prime }$ has weight $w_{m-i+1}$
• Then, we can leverage the correctness of the MST algorithm (prim’s or kruskal’s) in order to get the minimum spanning tree of this new weight-order-reversed-graph.
• The edges in this MST is the maximum spanning tree in the original graph
• Therefore, removing these edges we are left with the subset $F$ which is minimal

Complexity §

• negating weights: $O(m)$
• monotonically raising weights positive: $O(m)$
• MST algorith: $O(m\log n)$
• Total: $O(m\log n)$