Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs

By Mohammad Mahdian, Qiqi Yan. Symposium on the Theory of Computing, 2011

300 citations recorded by the source corpus.

In a seminal paper, Karp, Vazirani, and Vazirani show that a simple ranking algorithm achieves a competitive ratio of 1-1/e for the online bipartite matching problem in the standard adversarial model, where the ratio of 1-1/e is also shown to be optimal. Their result also implies that in the random arrivals model defined by Goel and Mehta, where the online nodes arrive in a random order, a simple greedy algorithm achieves a competitive ratio of 1-1/e. In this paper, we study the ranking algorithm in the random arrivals model, and show that it has a competitive ratio of at least 0.696, beating the 1-1/e ≈ 0.632 barrier in the adversarial model. Our result also extends to the i.i.d. distribution model of Feldman et al., removing the assumption that the distribution is known. Our analysis has two main steps. First, we exploit certain dominance and monotonicity properties of the ranking algorithm to derive a family of factor-revealing linear programs (LPs). In particular, by symmetry of the ranking algorithm in the random arrivals model, we have the monotonicity property on both sides of the bipartite graph, giving good "strength" to the LPs. Second, to obtain a good lower bound on the optimal values of all these LPs and hence on the competitive ratio of the algorithm, we introduce the technique of strongly factor-revealing LPs. In particular, we derive a family of modified LPs with similar strength such that the optimal value of any single one of these new LPs is a lower bound on the competitive ratio of the algorithm. This enables us to leverage the power of computer LP solvers to solve for large instances of the new LPs to establish bounds that would otherwise be difficult to attain by human analysis.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/c5529be3e186ec87d016e886764e6c2c2cdec5ee

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Secretary and Online Matching Problems with Machine Learned Advice (2020, background): “hich is the sum of all weights w r for which the corresponding ris matched in the online algorithm. This problem has both been studied under adversarial arrivals [20, 1] and uniformly random arrivals [34, 18]. In case the predictions are perfect, then, in order to nd a matching with the correspondin”
An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization (2014, methodology): “We also thank Marcin Mucha for showing us the work of Mahdian & Yan [26].”
Improved Online Algorithms for Knapsack and GAP in the Random Order Model (2020, methodology): “eralizations [13,30] are part of active research as well. The model has also been successfully applied to other problem classes including scheduling [3,21,40], packing [1,17,26,28,41], graph problems [9,27,34], facility location [38], budgeted allocation [39], and submodular welfare maximization [31”
A Joint Learning and Communications Framework for Federated Learning Over Wireless Networks (2019, background): “Hence, problem (23) can be solved by using bipartite matching algorithm [33].”
A Dynamic Near-Optimal Algorithm for Online Linear Programming (2009, unknown): “To be precise, consider the linear program maximize ∑n j=1 πjxj subject to ∑n j=1 aijxj ≤ bi, i = 1, . . . , m 0 ≤ xj ≤ 1 j = 1, . . . , n (1) where ∀j, πj ≥ 0, aj = (aij)mi=1 ∈ [0, 1]m, and b = {bi}mi=1 ∈ Rm.”
Secretaries with Advice (2020, methodology): “The technique has been extended to strongly factor revealing LPs by [25], who used it to analyze the KVV ranking algorithm for bipartite matching in the random order model.”
Online Matching and Ad Allocation (2013, methodology): “The proof in [73] uses a computer aided technique to solve a family of strongly factor revealing LPs, a technique that was introduced in [73], and shown to be useful for other problems also.”