Page 25 - 33-3

NTU Management Review Vol. 33 No. 3 Dec. 2023

In each iteration of GSAMF, we are given an original construction plan. We test each
unbuilt facility with each candidate scale level by calculating the benefit-to-cost ratio upon
adding it into the given construction plan. After choosing the one resulting in the highest
ratio, we proceed to the next iteration. We stop until all locations have been chosen or we

run out of budget. The pseudocode of the greedy selection algorithm with maximum flow
is presented in Algorithm 1.

Algorithm 1 Greedy Selection Algorithm with Maximum Flow (GSAMF)
1: y ← 0,S ← ∅
2: repeat
3: bestRatio ← 0,(j*,k*) ← (0, 0)
4: for j ∈ J \ S do
5: for k ∈ K do
6: if f(y) + f jk ≤ B then
7: y jk ←1
8: aRatio ← Ratio(j,k|y)
9: if aRatio > bestRatio then
10: bestRatio ← aRatio,(j*,k*)←(j,k)
11: end if
12: y jk ←0
13: end if
14: end if
15: end if
16: y j* k* ←1,S←S∪{ j* }
17: until (j*,k*)=(0,0)
18: return y

4.1.2 Time Complexity
Let V and E be the sets of the nodes and edges in the graph, the numbers of V and
E satisfy |V|≤|I|+|J||T|+2 and |E|≤|I||J||T|+|I|+|J||T|. A classic way to solve maximum flow
problem is to use the Edmonds-Karp algorithm proposed in Edmonds and Karp (1972),

which is an implementation of Ford-Fulkerson method using breadth-first search in finding
2
the augmenting path. The Edmonds-Karp algorithm provides a solution with a O(|V||E| )
bound. Therefore, in our problem, the time complexity of solving the maximum flow

2
problem is O(|V| |E| )=O(|I| |J| |T| ).
3
2
2
17