Description

(a) a typed preamble that contains (-2.5 pts if not included):
i. the list of people you worked with people for each question (if applicable),
ii. the sources you used,
iii. and if you wish, your impressions about the assignment (what was fun, what was difficult,
why…);
(b) your solutions for all problems, typed (not handwritten).
1 Fiber Connectivity
Formally, suppose we have: n cities, C = {c1,c2,··· ,cn}; m roads, R = {r1,r2,··· ,rm}, each connecting a pair of cities; and a constant k ∈ {2,…,|C| − 1}. If we are given a subset T of roads, T ⊆ R, then define dT(u) as the number of roads that city u is connected to using only roads in T. We want to find a subset T such that |T| ≤ |C| − 1 such that 1 ≤ dT(u) ≤ k for all nodes u ∈ C, and all cities in C are connected together.
Prove that this problem is NP-Complete.
2 Minimum Set Cover
The Minimum SET COVER problem (or SET COVER for short) is defined as follows: Given a set of elements U = {u1,u2,…,um} and a set of subsets of U, S = {S1,S2,…,Sn},Si ⊆ U,∀i = 1,…,n, find a subset S0 of S such that the union of the selected subsets covers all elements, SSi∈S0 Si = U and the number of selected subsets, |S0|, is minimized.
1. Devise a branch-and-bound algorithm for the Minimum SET COVER problem. This 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?
Do you think that your choices above will work well on typical instances of the problem? Why?
2. Outline a simple greedy heuristic for the SET COVER problem, and explain why it finds a valid solution and its running time.
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.
(a) What could be a possible scoring function for such candidate solutions?
(b) What would be a Neighborhood (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 Neighborhood (using Big-Oh)?
(c) Why would you consider adding Tabu Memory and what would be remembered in your Tabu Memory?
3 Optimizing Amazon’s Operations
X X
fi + mind(i,j)
i∈W
i∈W j∈{1,…,m}
1. Devise a branch-and-bound algorithm for this problem. This 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?
2. Outline a simple greedy heuristic for the problem, and explain why it finds a valid solution and its running time.
3. Imagine you wanted to use a local search method such as Simulated Annealing or Iterated Local Search to solve Amazon’s problem. Imagine a candidate solution is a subset of the locations.
(a) What could be a possible scoring function for such candidate solutions?
(b) What would be a Neighborhood (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 Neighborhood (using Big-Oh)?
(c) Why would you consider adding Tabu Memory and what would be remembered in your Tabu Memory?