CS 570 – HW 5
Due April 16, 2021 (by 4 AM Pacific Time)
1 Maximizing Profit (15 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 (with no wood resources leftover). However, this month there is a shortage of cabinet wood 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.
2 Dual Program (15 points)
Consider the following linear program:
max(3×1 + 2×2 + x3)
subject to
x1 − x2 + x3 ≤ 4 2×1 +x2 +3×3 ≤6 −x1 + 2×3 = 3 x1 + x2 + x3 ≤ 8 x1,x2,x3 ≥0
Write the dual problem. You do not need to demonstrate intermediate steps.
1
3 Spectrum Management (15 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 {(si,sj)} for some i,j ∈ [n]. 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.
4 Short Questions (15 points)
Prove or disprove the following statements.
5
1. 2. 3. 4.
5.
IfA≤p BandBisinNP-hard,thenAisinNP-hard.
IfA≤p BandBisinNP,thenAisinNP.
If 3-SAT ≤p 2-SAT, then P = NP.
Any NP problem can be solved in time O(2poly(n)), where n is the input size and poly(n) is a polynomial.
If a problem A ≤p B, then it follows that B ≤p A.
Finding a Satisfying Assignment (20 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.
2
6 Multi-Lane Highway (20 points)
The government wants to build a multi-lane highway across the country. The plan is to choose a route and rebuild the roads along this route. We model this problem with a simple weighted undirected graph with the nodes denoting the cities and the edges capturing the existing road network. The weight of an edge denotes the length of the road connecting the corresponding two cities.
Let duv denote the shortest path distance between nodes u and v.
Let d(v,P) denote the shortest path distance from a node v to the closest node on a path P (i.e. minduv).
u∈P
Next, we define the aggregate remoteness of P as r(P ) = d(v, P ).
v∈V
In the example shown in the figure below, path P = ABCD is the highway.
Then, d(A,P) = d(B,P) = d(C,P) = d(D,P) = 0, while d(X,P) = dXB = 2, d(Y,P) = dY B = 5, and, d(Z,P) = dZC = 7. The remoteness of path ABCD is 0 + 0 + 0 + 0 + 2 + 5 + 7 = 14.
The government wants a highway with the minimum aggregate remoteness, so that all the cities are somewhat close to the highway. Formally, we state the problem as follows, “Given a graph G, and a number k, does there exist a path P in G having remoteness r(P) at most k”? Show that this problem is NP-complete by reduction from the Hamiltonian Path problem.
3