Homework 4 Solution

    • Search Methods: Branch and Bound + Local Search (16 points)

Part 1: Devise a branch-and-bound algorithm for the Minimum SET COVER problem (you should know the de nition of this problem by now). Devising a Branch-and-bound for Min Set Cover entails deciding:

            (a) What is a subproblem?

            (b) How do you choose a subproblem to expand?

            (c) How do you expand a subproblem?

            (d) What is an appropriate lower bound at a search tree node?

Do you think that your choices above will work well on typical instances of the problem?

Why?

Part 2: Outline a simple greedy heuristic for the SET COVER problem, and explain why it nds a valid solution and its running time. (For this part it su ces to show the algorithm returns a feasible solution, no need to worry about the quality of the solution.)

Part 3: Imagine you wanted to use a local search method to solve Minimum SET COVER such as Simulated Annealing or Iterated Local Search. Imagine a candidate solution is a subset of the sets that might or might not cover all elements in the Universe set U.

        ◦ What could be a possible scoring function for such candidate solutions?

        ◦ What would be a Neighbourhood (or Moves) you would consider using for your local search to move from one candidate solution to other ’nearby’ solutions? How many potential neighbors can a candidate solution have under your Neighbourhood (using Big-Oh)?

        ◦ Why would you consider adding Tabu Memory and what would be remembered in your Tabu Memory?







1
    • Approximation algorithms{Make America Connected Again (12 points)

You are in charge of a community C with n people, who talk with each other regularly in person and with their friends on Facebook. Unfortunately, President Trump thinks it would be a good idea to build a wall around a subset of the people. He doesn’t really know which people to build a wall around, so he leaves it up to you to partition the community into two groups. However, you think this is a terrible idea. So while you must build the wall, you want to build the wall around the group of people that have the most connections (as measured by Facebook friendships) to the people remaining outside of the wall in order to mitigate the isolating e ect of the wall. But how can you do this?

More formally, if we have a set C of n people and a set F of Facebook friendships (i; j), where i and j are distinct persons, we want to nd a partition of C into two subsets C1 and C2 such that the number of Facebook friendships (i; j) where i 2 C1 and j 2 C2 is maximized. Let’s call this problem Make America Connected Again, or MACA.

After struggling with it for a while, you consult a friend, who unfortunately informs you that MACA is NP-hard. Bummer! However, unwilling to give up, you decide to investigate some approximation algorithms to help you solve the problem.

    (a) Devise a greedy algorithm that has an approximation ratio of 2. Give both the high level idea, and a pseudocode implementation of it.

    (b) Prove that your algorithm has an approximation ratio of 2.

    (c) Why isn’t your greedy solution optimal? Give an example where your greedy algorithm does not achieve the optimal, but achieves twice the optimal.

    (d) BONUS: prove that the decision version of MACA is NP-complete.


    • Modeling with ILP (12 points)

Formulate the following problems as integer linear programs. How many constraints and variables did you use?

    (a) The minimum set cover problem: Given a universe of m elements U and a collection of n subsets S1; S2; :::; Sn (Si U), nd the smallest number of subsets such that the union of their elements cover all of U.

    (b) Caleb and Karl are going camping together, and have two backpacks with capacity C liters. They have identi ed a set of k items, all of which are essential for the trip, and whose sizes s1; : : : ; sk are known. (You can assume the sum of the sizes of these k items is less than 2C.) Since Caleb and Karl are both about the same size, but Caleb is very slightly taller, they decide the fairest way to divide the items is so that each of them is carrying about the same size of items and if they are unequal, Caleb will carry

2

the heavier bag. Formulate an integer linear program to distribute the items between them so that the di erence in weight carried by Caleb and Karl is minimized.

    (c) Since Emily’s hummingbird cake mu ns were a resounding success, she is planning to participate in Atlanta Eats festival that lasts n days. The restaurants that will be at Atlanta Eats are inviting small businesses to cater their desserts. Emily plans to sell n di erent items at n di erent restaurant stalls over the festival. She will make exactly one batch of each item every day, and wants to organize her deliveries so that every day, each restaurant gets exactly one of the batches. She wants to make sure that each restaurant receives a di erent baked item every day of the festival. She has also already received some speci c requests that she has to satisfy as well: restaurant 1 wants item 3 on day 1 and item 4 on day 3, and restaurant 2 wants item 2 on day 2. Devise an ILP formulation to determine which item should be sent to each restaurant on each day of the festival. (Note there is no optimization objective, only constraints.)












































3