Premium
Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs
Author(s) -
Naparstek Oshri,
Leshem Amir
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20578
Subject(s) - bipartite graph , matching (statistics) , algorithm , auction algorithm , time complexity , random graph , hopcroft–karp algorithm , computer science , running time , path (computing) , computational complexity theory , blossom algorithm , 3 dimensional matching , graph , mathematics , combinatorics , theoretical computer science , pathwidth , line graph , auction theory , common value auction , statistics , revenue equivalence , programming language
Abstract In this paper we analyze the expected time complexity of the auction algorithm for the matching problem on random bipartite graphs. We first prove that if for every non‐maximum matching on graph G there exist an augmenting path with a length of at most 2 l + 1 then the auction algorithm converges after N ⋅ l iterations at most. Then, we prove that the expected time complexity of the auction algorithm for bipartite matching on random graphs with edge probability p = c log ( N ) Nand c > 1 is O (N log 2 ( N ) log ( N p ))w.h.p. This time complexity is equal to other augmenting path algorithms such as the HK algorithm. Furthermore, we show that the algorithm can be implemented on parallel machines with O ( log ( N ) ) processors and shared memory with an expected time complexity of O ( N log ( N ) ) . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 384–395, 2016