Infinite Galactic Builders Inc. has a problem. They need to call a company-wide meeting to discuss working relationships in the company, but they're going to lose lots of money for each person at the meeting. To minimize their losses, they want as few people as possible at the meeting, while making sure that each working relationship has at least one person present at the meeting. They have a list of all people working at the company, and a list of "works with" relationships that denote whether or not two employees work together in their duties at the company. Their goal is to find a minimal set of employees such that if (to take two hypothetical names) if Zlarg works with Z'norf, then at least one of Z'narg or Znorf is present at the meeting. a. (2 pts) The CEO Zmalin comes up with an idea to solve this problem: they randomly select an employee from a candidate list (which is initally all employees at the com- pany). If that employee doesn't work with anyone else going to the meeting, they are summoned to the meeting. Otherwise, their name is taken off the candidate list and they are not summoned. Find an example to show that Zmalin's algorithm can lead to arbitrarily bad results compared to the optimal solution. (Hint: With certain company structures, it can require nearly everyone to show up to the meeting.) b. (2 pts) After that fiasco, the CIO Zork steps in. Zork suggests instead of randomly sampling from the employees, they randomly sample from the "works with" list. When- ever they pull a relationship from the "works with" list, they summon both employees to the meeting. After this, they eliminate all relationships involving either employee from the "works with" list, repeating until the "works with" list is empty. Find an example to show that Zork's algorithm is also not optimal. c. (6 pts) Show that Zork's algorithm always gets within a factor of 2 of the optimal solution.
