Week Five

Question 1

PROBLEM: Weighted Interval Scheduling

Answer 1

Select a set C ⊆ R of requests such that sum of weights in C is maximized and no two requests from C conflict.

Question 2

PROBLEM: Subset Sum

Answer 2

Given a set {1, 2, . . . , n} of n items with weights and a bound W , find a set S of items such that
the sum of Weight(i) is maximized
subject to the constraint of being less than or equal to W.

Question 3

PROBLEM: Max Ind. Set

Answer 3

Given an undirected graph G = (V, E) on n vertices, find a set X of maximum size such that no vertices in X form an edge of G.