这是一篇澳洲的python算法代码代写

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 effffective 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

is minimized.

Sometimes to solve a given problem, it helps to solve a difffferent, related problem fifirst. 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 flflow network has a valid flflow with value at least as high as a specifified 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 flflow 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 k yp − xbk ≤ rp, then add an edge (up, vb) to E, and

set c(up, vb) = ∞.

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

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

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

(a) ”⇐ ”: assume that the output flflow network admits a flflow 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 flflow integrality we can assume that all flflow 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 flflow conservation.

To defifine a computer–station assignment g : P → B, for each p ∈ P, we use flflow 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 k yp − xbk ≤ 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. Defifine a flflow f on the max flflow 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-defifined.)

It can be seen by inspection of the reduction that the above steps assign a flflow 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 flflow, we nee d to check the flflow 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 infifinite 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 flflow 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 defifinition 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 defifinition 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 k yp−xg(p)k ≤ rp must be satisfified for g to be valid, and f(up, vb) = 1 exactly when g(p) = b, so fout(up) = 1 also.

It follows that f is a valid flflow 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 infifinite 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 k yp − xbk ≤ rp takes constant time.)

The last of these steps dominates, for a total running time of Θ(mn).

The the resulting flflow 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 flflow network has a max flflow 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 flflow 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]

↑ fifirst entry for which it’s possible

A is clearly a sorted list, so we could binary-search it for the fifirst 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 flflow 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.