Algorithms 3027 Assignment 4 Solution 2019 Semester 1
Task 1
1. Define a flow network G = (V, E) with integer capacities as follows:
• Vertices:
– Source and sink: s, t.
– For each position (i,j) in the mine, create a vertex vij.
The University of Sydney School of Computer Science
– Let Vo, Vg, Vd denote the vertices corresponding to open, gold and diamond vertices. • Edges:
– For each vertex v ∈ Vo, create an edge (s, v) with capacity 1.
– For each vertex u ∈ Vo, create an edge (u, v) with capacity 1, to each vertex v ∈ Vd ∪ Vg
if and only if u and v are orthogonally adjacent on the grid.
– For each vertex u ∈ Vd , create an edge (u, t) with capacity 2.
– For each vertex u ∈ Vg , create an edge (u, t) with capacity 1.
2. Use the Ford-Fulkerson algorithm to find an (integer-valued) maximum flow on this network. The value of this flow, M, is the minimal number of miners required to maximise the output of the mine.
3. Consider the set of edges {(u,v) | u ∈ Vo,v ∈ Vd ∪ Vg,f((u,v)) = 1}. Place a miner on the open space corresponding to u. The miner can mine from the space corresponding to v.
Task 2
Observations:
• No optimal solution can contain an idle miner, as removing the miner reduces the number of miners without reducing the amount of ore mined, contradicting the optimality of that solution. Henceforth, I will only consider arrangements where every miner is mining.
• An optimal solution can be represented by a many-to-one matching of open spaces (miners) to ore spaces (worked diamonds or gold).
M miners → M flow
Suppose M miners can work, then a matching of M open spaces to ore spaces exists. For each pair (open space, ore space) in that matching, consider the corresponding vertices u ∈ Vo and v ∈ Vd ∪ Vg . Add 1 flow to the edges (s, u), (u, v), and (v, t). All of these edges exist, because the miner must stand on an open space, they must mine an ore space, and the ore space must be orthogonally adjacent to the open space. (s,u,v,t) is an s-t path in G, so conservation of flow will be maintained. The capacity constraint is satisfied because:
• Only 1 miner can stand in each open space, u will apear in at most 1 pair of the matching, and thus (s, u), (u, v) will have flow at most 1.
• Gold spaces can only be mined by 1 miner, so will appear in at most 1 pair of the matching, so there will be at most 1 flow on (v, t);
• Diamond spaces can be mined by at most 2 miners, so there will be at most 2 flow on (v, t). Therefore the flow is valid. Furthermore, there is M flow out of s, so the flow has value M.
1
M miners ← M flow
Suppose a flow of value M exists. Then an integer valued flow with value M exists, by the Integrality Theorem. Consider the cut {s}∪Vo of G. The cutset of this cut is {(u, v) | u ∈ Vo, v ∈ Vd∪Vg}. By the flow value lemma, we know that the net flow across the cut is M. All the edges are outbound, have capacity 1, and the flow is integral, therefore the subset of this cutset with flow contains M edges. Consider an arrangement of miners where, for each such edge, a miner stands at the open space corresponding to u and mines the ore at the space corresponding to v. These spaces are orthogonally adjacent, because (u, v) exists. No open space contains more than one miner, because the inbound flow to u is at most 1. No gold space is worked by more than one miner, because the outbound flow of v is at most 1 in this case. No diamond space is worked by more than two miners, because the outbound flow of v is at most 2 in that case. Therefore, this matching of M open spaces to ore spaces satisfies the constraints of the problem, so M miners can work.
Mine placement ↔ Max flow
In summary, given any arrangement of active miners we can find a flow of the same size, and vice versa.
Therefore the optimal number of miners is equivalent to the maximum flow of the flow network.
Task 3
Transformation to flow:
• At most a2 + 2 ∈ O(a2) vertices are created.
• There no more than 5a2 ∈ O(a2) edges (no vertex has out-degree over 4, except s, which cannot have out-degree over a2).
• Building a graph is linear to the number of vertices and edges, so this takes O(a2) time. Solving the flow problem:
• Ford-Fulkerson finds a maximum flow in O(a2ko), because there are O(a2) edges and the flow out of s is bounded by ko.
Transformation to mining:
• A constant amount of work per edge, so this is O(a2) time.
Overall this is O(a2) ∪ O(a2ko) ∪ O(a2) = O(a2ko). (Note: solutions that have a final answer of O(a4) is good enough.)
2