CS计算机代考程序代写 algorithm COMP3X27 Flow Exemplar Solution

COMP3X27 Flow Exemplar Solution

Greg McLellan

April 29, 2021

T7 Problem 3: Base Station Load Balancing

First, a formal statement of the base station load balancing problem:

Input: A set B of base stations with a location xb ∈ R2 given for each station b ∈ B, and a set P of mobile
computers with a location yp ∈ R2 and effective transmission radius rp ∈ [0,∞) given for each p ∈ P .

Goal: Find a computer–station assignment g : P → B of computers to base stations, such that

• Each computer p is within range rp of the base station g(p) that it is assigned to; and

• The maximum load among all base stations

Lg := max
b∈B
|{p ∈ P | g(p) = b}| = max

b∈B
|g−1(b)|

is minimized.

Sometimes to solve a given problem, it helps to solve a different, related problem first. The above problem
is an optimization problem – we are trying to minimize the maximum load Lg over all admissible choices
of assignment g. Rather than solving this problem directly, we will instead start by considering a related
decision problem: given a set of base stations, a set of computers, and a desired max load L ∈ N, does there
exist an assignment g such that the load on each station is at most L?

Reduction to Max Flow

We reduce the decision version of the base station load balancing problem to the problem of determining
whether a flow network has a valid flow with value at least as high as a specified number K.

Each of the following sections refers to an arbitrary instance of the base station load balancing problem
given by a set B of base stations, a set P of mobile computers, and a desired max load L.

Description of reduction: Construct a flow network G = (V,E) with capacity function c as follows:

• Add a source vertex s and a sink vertex t to V .

• For each computer p ∈ P , add a vertex up to V and an edge (s, up) to E, and set c(s, up) = 1.

• For each base station b ∈ B, add a vertex vb to V and an edge (vb, t) to E, and set c(vb, t) = L.

• For each computer–station pair (p, b) ∈ P ×B, if ‖yp − xb‖ ≤ rp, then add an edge (up, vb) to E, and
set c(up, vb) =∞.

Finally, set the desired flow value to K = |P |.

1

Proof of correctness: Assume that the max flow instance outputted by our reduction is given by flow
network G = (V,E) with source s and sink t, capacity function c, and desired flow value K.

We prove that the original base station load balancing instance admits a valid computer–station assign-
ment with max load at most L, if and only if the max flow instance outputted by our reduction admits a
flow with value equal to K.

(a) ”⇐ ”: assume that the output flow network admits a flow f with value K. K is the maximum possible
flow value since

K = |P | = c({s}, V \ {s}),
i.e. K is the capacity of the source cut, so by flow integrality we can assume that all flow values
assigned to edges by f are integers. We can deduce that fout(up) = fin(up) = 1 for each computer
p ∈ P from the fact that the cut ({s}, V \ {s}) is saturated and from flow conservation.
To define a computer–station assignment g : P → B, for each p ∈ P , we use flow integrality and the
fact that fout(up) = 1 to observe that exactly one edge of the form (up, vb), for some b ∈ B, has a flow
value of 1. Using this fact, if f(up, vb) = 1 then we set g(p) = b. The existence of the edge (up, vb) in
G ensures that ‖yp − xb‖ ≤ rp, so this assignment is valid.
It remains to see that the load placed on each base station b ∈ B by g is at most L. To see this, observe
that each computer p with g(p) = b has f(up, vb) = 1, and that the total of such contributions is given
by

fin(vb) = fout(vb) ≤ c(vb, t) = L.
It follows that the max load assigned by g to any station is at most L.

(b) ”⇒”: assume that there is a valid computer–station assignment g for the base station load balancing
instance with max load at most L. Define a flow f on the max flow instance as follows:

1. Set f(s, up) = 1 for each computer p ∈ P ;
2. For each computer–station pair (p, b) ∈ P × B for which (up, vb) is an edge, set f(up, vb) = 1 if

g(p) = b, and f(up, vb) = 0 otherwise.

3. Set f(vb, t) = fin(vb) for each base station b ∈ B. (Having followed the previous step, fin(vb) is
well-defined.)

It can be seen by inspection of the reduction that the above steps assign a flow value to each edge in
G.

Clearly f saturates the source cut, so v(f) = c({s}, V \ {s}) = |P | = K.
To establish that f is a valid flow, we nee d to check the flow constraints.

(i) f(e) ≤ c(e) for every edge e ∈ E: clear for edges of the form (s, up) since they are all assigned
flow equal to their capacity; and a non-issue for edges of the form (up, vb) since all of these edges
have infinite capacity.

It remains to check edges of the form (vb, t) for each station b ∈ B. For such an edge, the capacity
is L, and the flow assigned is fin(vb), which is constituted of contributions of 1 from each edge of
form (up, vb) such that g(p) = b. The amount of computers p such that g(p) = b is the definition
of the load placed on b by g, which by assumption can’t be greater than L. It follows that

f(vb, t) = fin(vb) ≤ L = c(vb, t)

as required.

(ii) fin(u) = fout(u) for every u ∈ V (excluding s and t): for vertices of the form vb for some base
station b ∈ B, this follows immediately from the definition of f .
For each vertex of the form up for some computer p ∈ P , fin(up) = 1. The edge (up, vg(p)) is
guaranteed to exist in G since ‖yp−xg(p)‖ ≤ rp must be satisfied for g to be valid, and f(up, vb) = 1
exactly when g(p) = b, so fout(up) = 1 also.

2

It follows that f is a valid flow of value K as required.

Time complexity analysis: If |B| = m and |P | = n, then constructing an adjacency list representation
of G takes Θ(mn) time, since

• Add a source and sink to G takes constant time;

• Adding a vertex up and an edge the form (s, up) with capacity 1 for each p ∈ P takes Θ(n) time;

• Adding a vertex vb and edge (vb, t) with capacity L for each b ∈ B takes Θ(m) time;

• Adding an edge of the form (up, vb) with infinite capacity where applicable for each (p, b) ∈ P × B
takes Θ(|P × B|) = Θ(nm) time, assuming we iterate over every pair in P × B. In the worst case all
such edges may be required, so we can’t beat Ω(nm) here. (Here we make the assumption that the
arithmetic required to check whether ‖yp − xb‖ ≤ rp takes constant time.)

The last of these steps dominates, for a total running time of Θ(mn).
The the resulting flow network consists of |P |+ |B|+ 2 = n+m+ 2 ∈ Θ(m+n) vertices and |P |+ |B|+

|P ×B| = n + m + nm ∈ Θ(mn) edges in the worst case.
As the flow network has a max flow of ≤ C := c({s}, V \ {s}) = |P | = n, the Ford-Fulkerson algorithm

using any reasonable (i.e. linear-time) augmenting path selection strategy would solve our max flow instance
within O(|E|C) = O(mn · n) = O(mn2) time.

Solving the optimization problem

Our original aim was to minimize the maximum load Lg over all possible choices of computer–station
assignment g. Having solved the decision problem of determining whether a computer–station assignment
keeping the max load within some parameter L is possible, we can now solve the optimization problem of
determining the minimum such L, by using a binary search over possible L values.

In more detail, we could imagine an array A, which, for each index L, stores at A[L] a 0 if it’s impossible
to validly balance all the computers in P across the stations in B so that the max load is at most L, or a 1
if it is possible. Then A looks something like the following:

A = [0, 0, 0, . . . , 0, 0,0, 1, 1, 1, . . . , 1, 1]

↑ first entry for which it’s possible

A is clearly a sorted list, so we could binary-search it for the first index L such that A[L] = 1, i.e. the
lowest L such that there is a computer–station assignment with max load within L.

This search doesn’t require A to actually exist in memory – whenever our search needs to know A[L]
for some L, we can just carry out the reduction for the decision problem with L plugged in, and solve the
resulting flow network – although that means that each ”index lookup” will take O(mn2) time. L = n is an
obvious largest max load that must work if a valid computer–station assignment is possible at all, so this
search process takes O(mn2 log n) time in total.

3