## 3 Preliminaries and Problem Statement
### Greedy Algorithms  
The moving object coverage problem is unlikely to be solvable by a brute force approach. Because \(\frac{n}{m}\) zones are present and each sensor must move to a unique position in each zone, the total number of feasible movements for \(m\) sensors is \((mt!)^{\frac{n}{m}-1}\). Therefore, some greedy algorithms are required to solve the moving object coverage problem. Consider a simple bipartite matching method for mapping sensor positions in two neighboring zones. We generate a weighted complete bipartite graph where a node represents a sensor position and where the weight between two nodes is the distance between sensor positions in neighboring zones (Figure 2). The moving object coverage problem can now be formulated as a sequence of \((\frac{n}{m}-1)\) complete weighted bipartite graphs, where each set of two consecutive zones, except the base station, forms a complete bipartite graph (Figure 3). In this paper, we propose distinct greedy algorithms according to weighted bipartite matching methods for the moving object coverage problem under different objective functions. We solve the problem from two perspectives, designated as cases 1 and 2: (1) minimizing the total traveled distance and (2) minimizing the farthest traveled distance of mobile sensors. The proposed greedy solutions are used as bases for comparison. The effects of solving the moving object coverage problem from the two perspectives can be described as follows. In case 1, the moving object coverage problem can be divided into \((\frac{n}{m}-1)\) minimum weighted bipartite matching problems on a complete bipartite weighted graph. Given a bipartite graph \(G=(U,V,E)\), the minimum weighted bipartite matching problem involves finding a matching in which the sum of the edge weights is minimized. Each minimum  
Figure 3: Illustration of a sequence of complete bipartite graphs in the moving object coverage problem. Figure 2: Complete bipartite graph and matching diagram. weighted bipartite matching problem is clearly independent. Therefore, we can merge the solutions of \((\frac{n}{m}-1)\) minimum bipartite matching problems to establish the optimal solution for the moving object coverage problem with the goal of minimizing the total traveled distance. We use the Hungarian algorithm [39], a well-known combinatorial optimization method, for solving the weighted bipartite matching problem. Our proposed Algorithm 1 is presented as follows below. ```
0:\(P\), \(m\), \(n\)
0: A set \(M\) of minimum weight matchings of sensor spots
1: Partition \(P\) into \(V_{1}\), \(V_{2}\),..., \(V_{h}\) zones, where \(h=\frac{n}{m}\) and \(V_{i}=\{(i-1)\cdot m+1,\)..., \(i\cdot m\}\), \(1\leq i\leq h\)
2:\(M=\varphi\)
3:\(i=1\)
4:while\(i<h\)do
5: Construct a weighted complete bipartite graph \(G_{i}=(V_{i}\), \(V_{i+1}\), \(E)\), where \(E\) refers to the weighted edges between \(V_{i}\) and \(V_{i+1}\). 6: Find the minimum weight matching \(M_{i}\) of \(G_{i}\) by using the Hungarian method
7:\(M=M\cup M_{i}\)
8:\(i=i+1\)
9:endwhile
10:return\(M=\{M_{1},\)\(M_{2},\)..., \(M_{h-1}\}\)
```  
**Algorithm 1**Greedy_minimum_weight_matching  
The time complexity of the greedy minimum weight matching algorithm, designated as Greedy_MWM, is as follows. As noted in [39], the time complexity of the Hungarian method for solving the minimum weighted bipartite matching problem of a weighted complete bipartite graph is \(O(m^{3})\). Therefore, the total time complexity is \(O(nm^{2})\). In case 2, we solve the moving object coverage problem by solving \((\frac{n}{m}-1)\) weighted bottleneck bipartite matching problems on a complete weighted bipartite graph. Given a bipartite graph \(G=(U,V,E)\), the weighted bottleneck bipartite matching problem entails finding a perfect matching in which the maximum edge weight is minimized. We use the method proposed by [PERSON] and [PERSON] [40] to find this perfect matching in the Euclidean plane.