For two matroids ( M _1 ) and ( M _2 ) defined on the same ground set E, the online matroid intersection problem is to design an algorithm that constructs a large common independent set in an online fashion. The algorithm is presented with the ground set elements one-by-one in a uniformly random order. At each step, the algorithm must irrevocably decide whether to pick the element, while always maintaining a common independent set. While the natural greedy algorithm—pick an element whenever possible—is half competitive, nothing better was previously known; even for the special case of online bipartite matching in the edge arrival model. We present the first randomized online algorithm that has a ( 1 2 + ) competitive ratio in expectation, where ( >0 ) is a constant. The expectation is over the random order and the coin tosses of the algorithm. As a corollary, we also obtain the first linear time algorithm that beats half competitiveness for offline matroid intersection.
On the other hand, for uniformly random edge arrival Konrad, Magniez, and Mathieu @cite_29 gave the first single pass algorithm that obtains a @math -competitive ratio for bipartite matching in the semi-streaming setting. Their algorithm crucially used the ability to revoke earlier decisions. One of the contributions in this paper is to show that a variant of the greedy algorithm, which appears simple in hindsight, achieves a competitive ratio better than half in the more restrictive online model.
@cite_29
1871809785
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 , 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. We present three semi-streaming algorithms for Maximum Bipartite Matching with one and two passes. Our one-pass semi-streaming algorithm is deterministic and returns a matching of size at least 1 2 + 0.005 times the optimal matching size in expectation, assuming that edges arrive one by one in (uniform) random order. Our first two-pass algorithm is randomized and returns a matching of size at least 1 2 + 0.019 times the optimal matching size in expectation (over its internal random coin flips) for any arrival order. These two algorithms apply the simple Greedy matching algorithm several times on carefully chosen subgraphs as a subroutine. Furthermore, we present a two-pass deterministic algorithm for any arrival order returning a matching of size at least 1 2 + 0.019 times the optimal matching size. This algorithm is built on ideas from the computation of semi-matchings. We study the online stochastic matching problem in a form motivated by Internet display advertisement. Recently, gave an algorithm that achieves 0.6702 competitive ratio, thus breaking through the 1-1 e barrier. One of the questions left open in their work is to obtain a better competitive ratio by generalizing their two suggested matchings (TSM) algorithm to d-suggested matchings (d-SM). We show that the best competitive ratio that can be obtained with the static analysis used in the d-SM algorithm is upper bounded by 0.76, even for the special case of d-regular graphs, thus suggesting that a dynamic analysis may be needed to improve the competitive ratio significantly. We make the first step in this direction by showing that the RANDOM algorithm, which assigns an impression to a randomly chosen eligible advertiser, achieves 1 - e-ddd d! = 1-O(1 √d) competitive ratio for d-regular graphs, which converges to 1 as d increases. On the hardness side, we improve the upper bound of 0.989 on the competitive ratio of any online algorithm obtained by to 1-1 (e + e2) ≅ 0.902. Finally, we show how to modify the TSM algorithm to obtain an improved 0.699 approximation for general bipartite graphs. We present an approximation algorithm to find a weighted matching of a graph in the one-pass semi-streaming model. The semi-streaming model forbids random access to the input graph and restricts the memory to @math bits where n denotes the number of the vertices of the input graph. We obtain an approximation ratio of 5.58 while the previously best algorithm achieves a ratio of 5.82.