China
Africa
Explore chapters and articles related to this topic
Policy-Based Distributed Spectrum Allocation
Published in Anna Maria Vegni, Dharma P. Agrawal, Cognitive Vehicular Networks, 2018
Flavio Esposito, Donato Di Paola
To our knowledge, the first auction algorithm solving a resource allocation problem was proposed in 1988 by Bertsekas [2] as a polynomial-time algorithm to solve a single-assignment problem. The algorithm was centralized. Further modifications to the algorithm have been later proposed for multi-assignment problems and decentralized solutions.
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.
State-of-the-Art Auction Algorithms for Multi-depot Bus Scheduling Problem Considering Depot Workload Balancing Constraints
Published in Fuzzy Information and Engineering, 2020
The auction algorithm is modified to solve the multi-assignment problem (7)–(8). Start with a multi-assignment and pair satisfying (15), perform forward auction until each depot is assigned to a path. The multi-assignment satisfies (15), However some paths may not be assigned. Let and λ remains fix until the end of the algorithm. Then start with the results of the forward auction, apply a modified reverse auction algorithm as depicted in Figure 4. In Figure 4, is the number of assigned paths to depot k in iteration l.
Parallel Resource Allocation and Subcarrier Assignment for Downlink OFDMA
Published in IETE Technical Review, 2019
Satyendra Singh Yadav, Paulo Alexandre Crisóstomo Lopes, Sarat Kumar Patra
The existing popular algorithms like amplitude craving greedy (ACG), rate craving greedy (RCG) [15], RPO [16], improved ACG [24], and Hungarian [17, 25–27] perform only task-2. Prior to these algorithm either BABS [15] or BARE [16] algorithm is used for task-1. These two different algorithms for two different task makes the system computationally complex. This motivated us to develop an algorithm to perform both the tasks jointly with the advantage of reduced computational complexity. One solution to reduce the execution time of the existing algorithms is also found in the literature. The existing algorithms were implemented in parallel and computed on multi-core architecture to reduce the execution time. Vasconcelos and Rosenhahn [28] presented the Auction algorithm for the assignment problem with the advantage of parallel computation over Hungarian algorithm on graphics processing unit (GPU). In a similar fashion, Bertsekas and Castañon [29] presented a parallel asynchronous implementation of the Hungarian method for solving the classical assignment problem in graph theory and has achieved a remarkable reduction in the execution time. In the majority of these works, the multi-core architectures were used to reduce the execution time [30–32]. Hence the aim of this work is to develop a new parallel algorithm for both tasks and implement the Hungarian algorithm on parallel architectures.