Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs1. Issue 2 (23rd December 2014)

• Record Type: Journal Article
• Authors: Naparstek, Oshri; Leshem, Amir
• Is Part Of: Random structures & algorithms. Volume 48:Issue 2(2016)
• Page Start: 384
• Page End: 395
• Publication Date: 2014-12-23
• Subjects: complexity -- auction algorithm -- Pushrelabel algorithm -- Bipartite matching -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20578
• Languages: English
• ISSNs: 1042-9832

Abstract

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 ) N and 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