Question

Maximum-weight independent set.

(a) Prove that the two greedy algorithms, optimal substructure and activity selection are equivalent. That is, they return the same output for a given input.

(b) Prove that Greedy 2 returns an optimal solution to the maximum weight independent set problem by application of lemmata.

Answer 1

Algorithms for optimization problems typically go through a sequence of steps, with a set of choices at each step. For many optimization problems, using dynamic programming to determine the best choices is overkill, simpler, more efficient algorithms will do.

A greedy algorithm always makes the choice that looks best at the moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.

(a) A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. This property is a key ingredient of assessing the applicability of dynamic programming as well as greedy algorithms. As an example of optimal substructure, demonstrated that if an optimal solution A to the activity selection problem begins with activity 1, then the set of activities A' = A - {1} is an optimal solution to the activity-selection problem S' = {i € S : s_i >= â₁}.

A unit-time task is a job, such as a program to be run on a computer, that requires exactly one unit of time to complete. Given a finite set S of unit-time tasks, a schedule for S is a permutation of S specifying the order in which these tasks are to be performed. The first task in the schedule begins at time 0 and finishes at time 1, the second task begins at time 1 and finishes at time 2, and so on. Thus, as the greedy algorithm is given the optimal solution and works with optimal substructure they return the same output for a given input.

(b) Many problems for which a greedy approach provides optimal solutions can be formulated in terms of finding a maximum-weight independent subset in a weighted matroid. That is, we are given a weighted matroid , and we wish to find an independent set, such that w(A) is maximized. We call such a subset that is independent and has maximum possible weight an optimal subset of the matroid. Because the weight w(x) of any element x € S is positive, an optimal subset is always a maximal independent subset--it always helps to make A as large as possible.

By Lemma , any elements that are passed over initially because they are not extensions of can be forgotten about, since they can never be useful. Once the first element x is selected, Lemma implies that GREEDY does not err by adding x to A, since there exists an optimal subset containing x. Finally, Lemma implies that the remaining problem is one of finding an optimal subset in the matroid M' that is the contraction of M by x. After the procedure GREEDY sets A to{x}, all of its remaining steps can be interpreted as acting in the matroid , because B is independent in M' if and only if B {x} is independent in M, for all sets . Thus, the subsequent operation of GREEDY will find a maximum-weight independent subset for M', and the overall operation of GREEDY will find a maximum-weight independent subset for M.