Computational Science & Engineering (CSE) Algorithms Homework 4

CSE6140 
Computational Science & Engineering (CSE)
Algorithms
Homework 4
1 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 definition 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 finds a valid solution and its running time. (For this part it suffices 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
2 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 effect 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 find a partition of C into two subsets C1
and C2 such that the number of Facebook friendships (i, j) where i ∈ C1 and j ∈ 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.
3 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), find 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 identified 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 difference in weight carried by Caleb and Karl is minimized.
(c) Since Emily’s hummingbird cake muffins 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 different items at n different 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 different baked item every day of the festival. She has
also already received some specific 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