Description
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.
1. If A ≤p B and B is in NP-hard, then A is in NP-hard.
2. If A ≤p B and B is in NP, then A is in NP.
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.
5 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. min
u∈P
duv).
Next, we define the aggregate remoteness of P as r(P) = P
v∈V
d(v, P).
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
