Page 26 - 33-3

Time Complexity
4.1.2
Let and be the sets of the nodes and edges in the graph, the numbers of
and satisfy | | | | | || | and | | | || || | | | | || |. 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 the augmenting path. The Edmonds-Karp
algorithm provides a solution with a | || | ) bound. Therefore, in our problem,
�
the time complexity of solving the maximum flow problem is
| || | ) = | | | | | | ).
�
�
�
�
Optimal Allocation of Capacitated Facilities Considering Time-Dependent User Preference for User Number
Maximization � � �
In each iteration, our algorithm spends | | | | | | ) to compute the number
of the customers served by the construction plan. The algorithm runs for at most | |
In each iteration, our algorithm spends O(|I| |J| |T| ) to compute the number of the
2
3
3
iterations. In the iteration, it solves at most | | )| | maximum flow
customers served by the construction plan. The algorithm runs for at most |J| iterations. In
��
th
the j iteration, it solves at most (|J|-j+1)|K| maximum flow problems, each with j facility
problems, each with facility nodes in the graph, which means the complexity of
th
nodes in the graph, which means the complexity of completing the j iteration is O(|I| 2
J |T| ). Therefore, the total time complexity is | | ). Therefore, the total time complexity is
3
3
� �
��
�
completing the iteration is | |
|�|
facility nodes and edges. More precisely, adding a new edge is equivalent to changing
�� | | ) | | | | | | )� = | | | | | | | |).
�
�
� �
�
�
���
one edge’s capacity from zero to some positive number on the previous solved graph.
4.1.3 Incremental Maximum Flow
The difference between previous maximum flow and the new one will only be
Incremental Maximum Flow
4.1.3 In each iteration of GSAMF, we try all unbuilt facilities to add one into the
determined by those vertices affected by this insertion. Therefore, whenever we add a
construction plan with solving the maximum flow problem, which takes long
computational time. However, in our algorithm, there are only slight changes of the
new facility into the construction plan, instead of creating a whole new graph, we add
In each iteration of GSAMF, we try all unbuilt facilities to add one into the
graph comparing to those in previous iterations; most of the flows are still the same. We
vertices and edges to the previous solved graph and then continue solving the maximum
construction plan with solving the maximum flow problem, which takes long
only need to find new augmenting path and the backward path after adding new facility
nodes and edges. More precisely, adding a new edge is equivalent to changing one edge’s
flow problem.
computational time. However, in our algorithm, there are only slight changes of the
capacity from zero to some positive number on the previous solved graph. The difference
graph comparing to those in previous iterations; most of the flows are still the same.
Kumar and Gupta (2003) propose an incremental algorithm for the maximum flow
between previous maximum flow and the new one will only be determined by those
vertices affected by this insertion. Therefore, whenever we add a new facility into the
problem of inserting an edge in the graph. The time complexity of the algorithm is
We only need to find new augmenting path and the backward path after adding new
construction plan, instead of creating a whole new graph, we add vertices and edges to the
25
, where is the number of affected vertices and is the number of
�
previous solved graph and then continue solving the maximum flow problem.

Kumar and Gupta (2003) propose an incremental algorithm for the maximum
edges. When an edge is inserted into the graph, there may exist new augmenting path
flow problem of inserting an edge in the graph. The time complexity of the algorithm is
from source to sink through the new edge. The affected vertices are those that lie on at
O(|∆V| |E|), where |∆V| is the number of affected vertices and |E| is the number of edges.
2
When an edge is inserted into the graph, there may exist new augmenting path from
least one augmenting path. That is, when we add a new facility into the construction
source to sink through the new edge. The affected vertices are those that lie on at least
plan, it is equivalent to insert edges, i.e., , for all , to the graph and
one augmenting path. That is, when we add a new facility j into the construction plan, it is
��
equivalent to insert |T| edges, i.e., (f ,d) for all t ∈ T, to the graph and each insertion affects
jt nodes. Therefore, the total time complexity
each insertion affects
|∆V|=O(|I|+3) nodes. Therefore, the total time complexity of adding a new facility to the
of adding a new facility to the graph is
graph is
O �� � � ,
�
�
�
�
and the total time complexity is 18
�
�� − � .
�
�
�
�
�
���
The implementation with incremental maximum flow indeed reduces the time
complexity of GSAMF.
26