Your friends are involved in a large-scale atmospheric science experiment. They
ID: 3762772 • Letter: Y
Question
Your friends are involved in a large-scale atmospheric science experiment. They need to get good measurements on a set S of n different conditions in the atmosphere (such as the ozone level at various places), and they have a set of m balloons that they plan to send up to make these measurements. Each balloon can make at most two measurements. Unfortunately, not all balloons are capable of measuring all conditions, so for each balloon i = 1, . . . , m, they have a set Si of conditions that balloon i can measure. Finally, to make the results more reliable, they plan to take each measurement from at least k different balloons. (Note that a single balloon should not measure the same condition twice.) They are having trouble figuring out which conditions to measure on which balloon. Example. Suppose that k = 2, there are n = 4 conditions labeled c1, c2, c3, c4, and there are m = 4 balloons that can measure conditions, subject to the limitation that S 1 = S2 = {c1, c2, c3}, and S3 = S4 = {c1, c3, c4}. Then one possible way to make sure that each condition is measured at least k = 2 times is to have . balloon 1 measure conditions c 1, c2, . balloon 2 measure conditions c 2, c3, . balloon 3 measure conditions c 3, c4, and . balloon 4 measure conditions c 1, c4. (a) Give a polynomial-time algorithm that takes the input to an instance of this problem (the n conditions, the sets Si for each of the m balloons, and the parameter k) and decides whether there is a way to measure each condition by k different balloons, while each balloon only measures at most two conditions.(b) You show your friends a solution computed by your algorithm from (a), and to your surprise they reply, “This won’t do at all—one of the conditions is only being measured by balloons from a single subcontractor.” You hadn’t heard anything about subcontractors before; it turns out there’s an extra wrinkle they forgot to mention. . . . Each of the balloons is produced by one of three different subcontractors involved in the experiment. A requirement of the experiment is that there be no condition for which all k measurements come from balloons produced by a single subcontractor. For example, suppose balloon 1 comes from the first subcontractor, balloons 2 and 3 come from the second subcontractor, and balloon 4 comes from the third subcontractor. Then our previous solution no longer works, as both of the measurements for condition c 3 were done by balloons from the second subcontractor. However, we could use balloons 1 and 2 to each measure conditions c 1, c2, and use balloons 3 and 4 to each measure conditions c 3, c4. Explain how to modify your polynomial-time algorithm for part (a) into a new algorithm that decides whether there exists a solution satisfying all the conditions from (a), plus the new requirement about subcontractors.
Explanation / Answer
egin{center}
egin{tikzpicture}
GraphInit[vstyle=Normal]
SetGraphUnit{1}
ikzset{VertexStyle/.style = {shape = none,text = blue!40 }}
Vertex[x=1.5,y=4.2]{2}
Vertex[x=4.5,y=4.2]{1}
Vertex[x=7.5,y=4.2]{$k$}
ikzset{LabelStyle/.style = {draw}}
ikzset{VertexStyle/.style = {shape = circle,
fill = blue!20,
minimum size = 20pt,
text = black,
draw}}
ikzset{EdgeStyle/.style = {TempStyle, ->}}
Vertex[x=0,y=2]{s}
Vertex[x=3,y=3.5,L=$S_1$]{A1}
SO[L=$S_2$](A1){A2}
SO[L=$S_3$](A2){A3}
SO[L=$S_2$](A3){A4}
ikzset{EdgeStyle/.append style = {bend left=10}}
Edge(s)(A1)
Edge(s)(A2)
ikzset{EdgeStyle/.append style = {bend right=10}}
Edge(s)(A3)
Edge(s)(A4)
Vertex[label=$c_1$,x=6,y=3.5, L=$C_1$]{B1}
SO[L=$C_2$](B1){B2}
SO[L=$C_3$](B2){B3}
SO[L=$C_4$](B3){B4}
ikzset{EdgeStyle/.append style = {bend left=0}}
Edge(A1)(B1)
Edge(A1)(B2)
Edge(A2)(B2)
Edge(A2)(B3)
Edge(A3)(B3)
Edge(A3)(B4)
Edge(A4)(B4)
Edge(A4)(B1)
Vertex[x=9,y=2]{t}
ikzset{EdgeStyle/.append style = {bend left=10}}
Edge(B1)(t)
Edge(B2)(t)
ikzset{EdgeStyle/.append style = {bend right=10}}
Edge(B3)(t)
Edge(B4)(t)
end{tikzpicture}
end{center}
claimstar If we cast the problem as a network, then deciding if there is a way to measure each condition $k$ times is equivalent to determining if the maximum flow of the graph is equal to $k cdot |C|$.
proof
Let the flow in the graph represent the number of measurements taken. The constraints are as follows:
egin{enumerate}
item Each balloon takes at most $2$ measurements.
item Each balloon takes each measurement at most once.
item Each measurement must be taken at least $k$ times.
end{enumerate}
>We encode the constraints as the capacities of groups of edges. For the first constraint, since each balloon should have a maximum flow of $2$ through it, we say that the single incoming edge will have capacity 2. For the second constraint since each balloon should take each measurement at most once, each edge from a balloon to a measurement will have capacity 1.
>Finally consider the last constraint, we want to ensure that each measurement is taken at least $k$ times. Therefore we bound the flow through each measurement node to $k$, and if under maximum flow each of the $k$ weighted edges are saturated then we can take $k$ observations of each measurement. But this is exactly the same as if the maximum flow is equal to $k cdot |C|$.
mkstar By the Ford Fulkerson algorithm we can find the maximum flow of the proposed graph in $O(|S| cdot E)$ where $E$ is the number of edges, specifically: $$E = |S| + |C| + sum_{S_i in S} |S_i|. $$
subsection*{b}
Suppose that each of the balloons is produced by one of three different sub-contractors involved in the experiment. A requirement of the experiment is that there be no condition for which all $k$ measurements come from balloons produced by a single subcontractor. Explain how to modify your polynomial-time algorithm for part (a) into a new algorithm that decides whether there exists a solution satisfying all the conditions from (a), plus the new requirement about subcontractors. \
% Solution
oindentmakebox[ extwidth]{%
egin{tikzpicture}
GraphInit[vstyle=Normal]
SetGraphUnit{1}
ikzset{VertexStyle/.style = {shape = none,
text = blue!40 }}
Vertex[x=1.5,y=4.2]{2}
Vertex[x=4.5,y=4.2]{1}
Vertex[x=7.5,y=4.2]{$k$}
Vertex[x=10.5,y=4.2]{$k-1$}
Vertex[x=13.5,y=4.2,L=$infty$]{inf}
ikzset{LabelStyle/.style = {draw}}
ikzset{VertexStyle/.style = {shape = circle,
fill = blue!20,
minimum size = 20pt,
text = black,
draw}}
ikzset{EdgeStyle/.style = {TempStyle, ->}}
Vertex[x=0,y=2]{s}
Vertex[x=3,y=3.5,L=$S_1$]{A1}
SO[L=$S_2$](A1){A2}
SO[L=$S_3$](A2){A3}
SO[L=$S_2$](A3){A4}
ikzset{EdgeStyle/.append style = {bend left=10}}
Edge(s)(A1)
Edge(s)(A2)
ikzset{EdgeStyle/.append style = {bend right=10}}
Edge(s)(A3)
Edge(s)(A4)
Vertex[label=$c_1$,x=6,y=3.5, L=$C_1$]{B1}
SO[L=$C_2$](B1){B2}
SO[L=$C_3$](B2){B3}
SO[L=$C_4$](B3){B4}
ikzset{EdgeStyle/.append style = {bend left=0}}
Edge(A1)(B1)
Edge(A1)(B2)
Edge(A2)(B2)
Edge(A2)(B3)
Edge(A3)(B3)
Edge(A3)(B4)
Edge(A4)(B4)
Edge(A4)(B1)
Vertex[label=$c_1$,x=9,y=3.5, L=$C_1'$]{C1}
SO[L=$C_2'$](C1){C2}
SO[L=$C_3'$](C2){C3}
SO[L=$C_4'$](C3){C4}
ikzset{EdgeStyle/.append style = {bend left=0}}
Edge(B1)(C1)
Edge(B2)(C2)
Edge(B3)(C3)
Edge(B4)(C4)
Vertex[x=12,y=3, L=$M_1$]{D1}
SO[L=$M_2$](D1){D2}
SO[L=$M_3$](D2){D3}
ikzset{EdgeStyle/.append style = {bend left=0}}
Edge(C1)(D1)
Edge(C1)(D2)
Edge(C2)(D1)
Edge(C2)(D2)
Edge(C3)(D2)
Edge(C3)(D3)
Edge(C4)(D2)
Edge(C4)(D3)
Vertex[x=15,y=2]{t}
ikzset{EdgeStyle/.append style = {bend left=10}}
Edge(D1)(t)
ikzset{EdgeStyle/.append style = {bend left=0}}
Edge(D2)(t)
ikzset{EdgeStyle/.append style = {bend right=10}}
Edge(D3)(t)
end{tikzpicture}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.