Counterexamples for Greedy Algorithms

Minimum Spanning Tree Problem

You should prepare your answers electronically, in a Word document or pdf file. Where mathematical formulas, diagrams etc are needed you can use handwriting and insert them into the document as pictures, but any substantial amount of text should be typeset and not handwritten. 

In line with university policy,  marking will be done anonymously.  Please do not include your name or other personally identifiable information in your submission.

In each of the following, a greedy algorithm is proposed for the given problem. Give a simple counterexample for each of them to show that the proposed greedy algorithm does not always return the optimal solution. You should (1) give an example input, (2) state the  solution returned by the greedy algorithm on that input, and (3) state the optimal solution (or indeed any better solution than the greedy one) for that input.

(a) Input: An undirected graph G(V, E).

Problem: Find a minimum spanning tree T of G.

Algorithm:
Choose an arbitrary vertex s in G

Initialise S := (s), T := () (empty set), and u := s while S /= V do

Find the minimum-weight edge e among all edges (u, v) where v is not in S

Add v to S, add e to T , and set u := v end while

(Note:  this is not Prim’s algorithm.)    [10 marks]

(b)Input: A set A of animals, and a set of pairs (ai, aj) indicating animal ai cannot be put together with animal aj (because for example ai attacks or eats aj).

Problem: Choose a subset Aj of animals from A so that the animals in Aj can be safely put together, and that the number of animals in Aj is as large as possible.

Algorithm: Initialise Aj to be empty. For each animal in A, count the number of other animals it can be safely put together. In decreasing order of this count, consider each animal in turn and add it to Aj  if it can be put safely together with all other animals already in Aj.    [10 marks]

(c)Input: A set of n tasks,  each with a required “amount” of “work”;  a set of  m workers all of whom can work on any of the tasks.

Problem:  Assign the  tasks  to  the  workers  so  that  the  work is  “distributed as  evenly as possible among the workers”, or more precisely, the amount of work assigned to the busiest worker (the one with the largest amount of work) is as small as possible.

Algorithm: Sort the tasks in decreasing order of amount of work. For each task in this sorted order, assign it to the worker who currently (i.e., based on the assignment made so far) has the least amount of work assigned.    [10 marks]