China
Africa
Explore chapters and articles related to this topic
Multi-Aerial-Robot Planning
Published in Yasmina Bestaoui Sebbane, Multi-UAV Planning and Task Allocation, 2020
The Hungarian algorithm treats the optimal assignment problem as a combinatorial problem in order to efficiently solve an n × n task assignment problem in 0(n3) time. The utility estimates become edge weights in a complete bipartite graph in which each robot and task becomes a vertex. The Hungarian algorithm pseudocode is shown in Algorithm 3; it searches for a perfect matching in a sub-graph of the complete bipartite graph, where the perfect matching is exactly the optimal assignment problem. In step 7, the search process either increases the matching size or the so-called equality graph in which the matching resides.
Achieving Scalability in the 5G-Enabled Internet of Things
Published in Yulei Wu, Haojun Huang, Cheng-Xiang Wang, Yi Pan, 5G-Enabled Internet of Things, 2019
Fuchun Joseph Lin, David de la Bastida
We use the Hungarian algorithm [25] to achieve this objective. The Hungarian algorithm utilizes a cost matrix C, which can be derived from the bipartite weighted graph G, where each element in the matrix represents the cost, E, of assigning the ith traffic pattern to the jth network slice. With the Hungarian algorithm, an optimal solution can be found by calculating the minimal cost of matching N traffic patterns with N network slices.
Object Tracking through Image Sequences
Published in Jeffrey P. Simmons, Lawrence F. Drummy, Charles A. Bouman, Marc De Graef, Statistical Methods for Materials Science, 2019
Song Wang, Yu Hongkai, Youjie Zhou, Jeffrey P. Simmons, Craig Przybyla
There are many bipartite matching algorithms that can find the global optimal solution in Step 4. The most widely used one is the Hungarian algorithm [517], which finds the optimal bipartite matching by iteratively performing vertex labeling and path augmenting to the underlying bipartite graph. The Hungarian algorithm has a time complexity of O((M+N)3).
A Generic Algorithm for Traversing a Directed Acyclic Graph: An Application to the Home Health Care Scheduling Problem
Published in IETE Journal of Research, 2022
Marouene Chaieb, Jaber Jemai, Dhekra Ben Sassi, Khaled Mellouli
Four main assignment algorithms are available in the literature and used to handle the assignment problem which are (i) the Hungarian algorithm (or Kuhn–Munkres algorithm); (ii) the primal simplex algorithm; (iii) the auction algorithm; and (iv) the quick match. In our context, we adopt the Hungarian method to solve the assignment component. Our choice is explained by the efficiency of the Hungarian algorithm in solving this kind of problem. The Hungarian algorithm was developed by Harold Kuhn [15] in 1955 to solve the assignment algorithm. The data instance used by the assignment component must be updated after handling the grouping subproblem because the assignment subproblem depends on the clustering component. The update algorithm will feed the set of clusters obtained as a solution of the grouping component solved previously to the instance of the assignment problem.
Recent Advancements in Semantic Web Service Selection
Published in IETE Journal of Research, 2022
Riddhi Pahariya, Lalit Purohit
The maximum matching algorithm plays a very vital role in the semantic web service selection process. Based on the various experimentations performed, it is concluded that the Ford Fulkerson and Edmond Karp Algorithm can be followed as a web services maximum matching algorithm in place of the Hungarian Algorithm. Ford Fulkerson Algorithm and Edmond Karp Algorithm have time complexity of O(VE2). On the other hand, the Hungarian Algorithm has a time complexity of O(V3E). Furthermore, the variation in the size of the data will also affect the time complexity. However, the network flow-based approach is complex for handling run time failure of web services. This affects web service availability. The proposed work is experimented with the atomic web service selection. Hence, based on the results obtained, in the future the network flow algorithm-based maximum matching will be tested with composite web services.
Survey: mobile sensor networks for target searching and tracking
Published in Cyber-Physical Systems, 2018
A typical task allocation deals with either single- or multiple-target tracking. There are usually two steps involved. First, a set of new positions is obtained for the sensors based on, for example, target positions, expected measurements and so on. Second, a combinatorial formulation is used to set up an assignment problem, which, in its most basic form, can be solved by the Hungarian algorithm. A centralised formulation for the assignment problem is where the sets of current and new sensor positions are and , respectively. Note that these do not have to be of equal size, as some sensors may not have to move. Each move is associated with a cost stored in the matrix C(i, j). Here we use a binary matrix (values 0 or 1) with entries denoted , which is 1 if the sensor at position i should move to position j and 0 otherwise.