CS 570 – HW 5 Solution
Due Friday, April 24 (by 23:30)
1 Maximizing Profit (10 points)
A furniture company produces three types of couches. The first type uses 1 foot of framing wood and 3 feet of cabinet wood. The second type uses 2 feet of framing wood and 2 feet of cabinet wood. The third type uses 2 feet of framing wood and 1 foot of cabinet wood. The profit of the three types of couches is $10, $8, and $5, respectively. The factory produces 500 couches each month of the first type, 300 of the second type, and 200 of the third type. However, this month there is a shortage of cabinet wood and the supply to the factory will have to be reduced by 600 feet, but the supply of framing wood is increased by 100 feet. How should the production of the three types of couches be adjusted to minimize the decrease in profit? Formulate this problem as a linear programming problem.
Solution:
Denote xi as the number of change of couches of type i. The change in profits is
10×1 + 8×2 + 5×3. The change in the amount of cabinet wood used is
3×1 +2×2 +x3 ≤ −600. The change in the amount of framing wood used is
x1 +2×2 +2×3 ≤100.
The number of each type of couch produced should be non-negative, we have
x1 ≥ −500, x2 ≥ −300, x3 ≥ −200.
The goal is to minimize the decrease (or maximize the increase) in profit. We
have the following linear programming:
1
Or equivalently,
max subject to
min subject to
10×1 + 8×2 + 5×3
3×1 + 2×2 + x3 ≤ −600, x1 +2×2 +2×3 ≤100, x1 ≥ −500,
x2 ≥ −300,
x3 ≥ −200.
−10×1 −8×2 −5×3
3×1 + 2×2 + x3 ≤ −600, x1 +2×2 +2×3 ≤100, x1 ≥ −500,
x2 ≥ −300,
x3 ≥ −200.
2
2 Dual Program (15 points)
Consider the following linear program:
max(3×1 + 2×2 + x3)
subject to
Write the dual problem.
Solution:
x1 − x2 + x3 ≤ 4 2×1 +x2 +3×3 ≤6 −x1 + 2×3 = 3 x1 + x2 + x3 ≤ 8 x1,x2,x3 ≥0
Rewrite the equality constraint −x1 + 2×3 = 3 as follows: −x1 + 2×3 ≤ 3
x1 − 2×3 ≤ −3
• Multiply each equation by a new variable yk ≥ 0.
y1(x1 −x2 +x3)≤4y1 y2(2×1 + x2 + 3×3) ≤ 6y2 y3(x1 +x2 +x3)≤8y3 y4(−x1 + 2×3) ≤ 3y4
y5(x1 − 2×3) ≤ −3y5
• Add up those equations.
y1(x1 −x2 +x3)+y2(2×1 +x2 +3×3)+y3(x1 +x2 +x3)+y4(−x1 +2×3)+y5(x1 −2×3) ≤4y1 +6y2 +8y3 +3y4 −3y5
• Collect terms with respect to xk.
x1(y1 +2y2 +y3 −y4 +y5)+x2(−y1 +y2 +y3)+x3(y1 +3y2 +y3 +2y4 −2y5)
≤4y1 +6y2 +8y3 +3y4 −3y5
3
• Chooseyk inawaythatATy≥c.
Note that bT = (4,6,8,3,−3) and cT = (3,2,1). The dual problem is:
subject to
min(4y1 +6y2 +8y3 +3y4 −3y5)
y1 +2y2 +y3 −y4 +y5 ≥3 −y1 + y2 + y3 ≥ 2 y1 +3y2 +y3 +2y4 −2y5 ≥ 1 y1,y2,y3,y4,y5 ≥ 0
Or equivalently, letting w = y4 − y5 unconstrained. The dual problem is:
subject to
min(4y1 + 6y2 + 8y3 + 3w)
y1 +2y2 +y3 −w≥3 −y1 + y2 + y3 ≥ 2 y1 + 3y2 + y3 + 2w ≥ 1 y1,y2,y3 ≥0
4
3 Spectrum Management (10 points)
Spectrum management is the process of regulating the use of radio frequencies to promote efficient use and gain a net social benefit. Given a set of broadcast emitting stations s1,…,sn, a list of frequencies f1,…,fm, where m ≥ n, and the set of adjacent stations E = {(si,sj)}. The goal is to assign a frequency to each station so that adjacent stations use different frequencies and the number of used frequencies is minimized. Formulate this problem as an integer linear programming problem.
Solution:
Note that n frequencies are enough to be assigned to any set of stations. We introduce n2 binary variables xij, for 1 ≤ i,j ≤ n, where xij denotes whether station si uses frequency fj. In addition, we introduce one binary variable uj for each frequency fj, denoting whether frequency fj is used or not. We have the following ILP:
subject to
n
minuk
x,u
k=1
∀jand∀(i,i′)s.t.(si,sj)∈E i∈[n]
i,j∈[n] i,j ∈ [n]
xij+xi′j ≤1, n
xij =1, j=1
xij ≤uj, uj,xij ∈ {0,1},
The first inequality means that adjacent stations should have different frequency. The second inequality means that one frequency for each station. The third inequality means we use active frequencies only.
5
4 Short Questions (15 points)
True or false? Shortly explain your answers.
1. IfA≤p BandBisinNP-hard,thenAisinNP-hard.
2. IfA≤p BandBisinNP,thenAisinNP.
3. If 3 − SAT ≤p 2 − SAT, then P = NP.
4. Any NP problem can be solved in time O(2poly(n)), where n is the input size and poly(n) is a polynomial.
5. If a problem A ≤p B, then it follows that B ≤p A.
Solution:
1. False. One can transform the empty language ∅ to any N P -hard problem, but the empty language is not NP-hard.
2. True. One can construct a certifier for A by composing the certifier for B and the polynomial reduction map.
3. True. Since 2−SAT is in P and 3−SAT is in NP and the reduction shows that 2 − SAT is in NP, we have P = NP.
4. True. Since one can use exponential time to try all possible certificates, each of them can be checked by a polynomial time deterministic Turing machine.
5. False. Let A be a problem in P and B be a problem that requires ex- ponential time to solve. If B ≤p A, then there exists a polynomial time algorithm for B, which leads to an contradiction.
6
5 Finding a Satisfying Assignment (10 points)
Assume that you are given a polynomial time algorithm that given a 3-SAT instance decides in polynomial time if it has a satisfying assignment. Describe a polynomial time algorithm that finds a satisfying assignment (if it exists) to a given 3-SAT instance.
Solution:
Given an instance of 3-SAT consisting of variables X = {x1 , . . . , xn } and clauses C1,…,Ck. Let φ(x1,…,xn) = C1 ∧ ··· ∧ Ck be the corresponding Boolean formula. Define φi and φi as the CNF formula obtained from φ by setting xi to TRUE and FALSE, respectively. Let A(φ) be the given algorithm that decides whether a given instance has a satisfying assignment. Suppose A(φ) returns TRUE if φ is satisfiable and FALSE otherwise. Note that φi is satisfiable if and only if φ has a satisfying assignment where xi = TRUE. Then the following algorithm constructs satisfying assignment for φ if possible, or returns that no such assignment exists.
• If A(φ) = FALSE, then return that φ not satisfiable. • Fori=1,…,n
– If A(φi) = TRUE ∗ φ ← φi
∗ xi ← TRUE – Else
∗ φ ← φi
∗ xi ← FALSE
• Return x = (x1,…,xn)
7
6 Shipping Goods (15 points)
Given n positive integers x1,…,xn. The Partition Problem asks if there is a subset S ⊆ [n] such that:
xi =xi. i∈S i̸∈S
It can be proven that the Partition Problem is NP-complete. You do not to prove it, but rather use it in the following problem.
Assume that you are consulting for a shipping company that ships a large amount of packages overseas. The company wants to pack n products with integer weights p1, . . . , pn into a few boxes as possible to save on shipping costs. However, they cannot put any number of products into a box due to the ship- ping capacity restriction. The total weight of products in each box should not exceed W ? You may assume that for each i-th product pi ≤ W . You task is to advise the company if n products can be placed into at most k < n boxes. Show that the problem is NP-Complete by reduction from the Partition Problem.
Solution:
1. Claim: this problem is in NP.
We can be verify whether n products are placed into at most k boxes such that the total weight of products in each box does not exceed W in linear time.
2. Claim: There is a subset S such that i∈S xi = i̸∈S xi if and only if n
products with weight pi = xi for all i can be placed into at most k = 2
boxes, where the weight of each box is no more than W = 1 pi. 2i
Letk=2andW=1pi,wherepi =xi. Ifthereisasolutionto 2i
the Partition problem, then the sum of elements in each of S and [n] \ S is W = 1 pi. By transforming these two subsets into two boxes, we
2i
have a solution to this problem. Conversely, if there is a solution to this
problem with 2 boxes and W = 1 pi, then all products are in those 2 2i
boxes and the total weight of them are the same. By transforming these two boxes into two subsets, we have a solution to the Partition problem.
Therefore, we can conclude that this problem is NP-complete.
8
7 Longest Path (15 points)
Given a graph G = (V,E) and a positive integer k, the longest-path problem is the problem of determining whether a simple path (no repeated vertices) of length k exists in a graph. Show that this problem is N P -complete by reduction from the Hamiltonian path.
Solution:
1. Claim: this problem is in NP.
A simple path of length k can be verified by traversing the path in linear time, including checking whether there is no repeated vertices, the length is k, and all edges of the path are in E.
2. Claim: G has a Hamiltonian path if and only if G has a simple path of length k = n − 1.
Given an instance of the Hamiltonian path problem: a graph with n ver- tices. Since a Hamiltonian path in G is equivalent to a simple path of length n − 1 in G, it turns out that there is a polynomial time reductions from the Hamiltonian path problem to this problem. Specifically, if there is a Hamiltonian path, then that path is a simple path of length n − 1. On the other hand, if there is a simple path of length n − 1, then it is a Hamiltonian path.
Therefore, we can conclude that this problem is NP-complete.
9
8 Helping with the COVID-19 Crisis (10 points)
Given an integer k, a set C of n cities c1,...,cn, and the distances between these cities dij = d(ci,cj), for 1 ≤ i < j ≤ n, where d is the standard Euclidean distance. We want to select a set H of k cities for building mobile hospitals in light of the coronavirus outbreak. The distance between a given city c and the set H is given by d(c,H) = minh∈H d(c,h). The goal is to select a set H of k cities that minimizes r = maxc∈C d(c,H). Namely, the maximum distance from a city to the nearest mobile hospital is minimized. Give a 2-approximation algorithm for this problem.
Solution:
Consider the following algorithm:
1. Assume k ≤ |C| (Otherwise define H = C)
2. Selectanycityc∈CandletH={c} 3. While |H| ≤ k
• Select a city c ∈ C that maximizes d(c,H) • AddcityctoH
4. Return H as the selected set of cities for building mobile hospitals
Claim: Let H∗ be an optimal set of k points. Then this algorithm returns a set H of k points such that maxc∈C d(c, H) ≤ 2 maxc∈C d(c, H∗).
Let r = maxc∈C d(c, H) and r∗ = maxc∈C d(c, H∗). We want to prove this is an 2-approximation by contradiction. Assume r > 2r∗.
Since r∗ < 1r, for each hi ∈ H, there is exactly one h∗i ∈ H∗ such that 2
d(hi, h∗i ) < 1 r. Consider any city c ∈ C and its closest hospital h∗j ∈ H∗. Then 2
d(c,H) ≤ d(c,hj) ≤ d(c,h∗j)+d(h∗j,hj) ≤ 2r∗. This contradicts the assumption that r > 2r∗. Hence r ≤ 2r∗.
10