2015/12/19 by Guru Guruganesh, Sahil Singla, Guruganesh, Guru +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.1512.06271
39 pages, 3 figures, 1 notation table, Part of this appeared in IPCO 2017
arxiv created 2018/02/19 · arxiv updated 2018/02/20
For two matroids M1 and M2 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 \frac12 + δ 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.