Online matroid intersection: Beating half for random arrival

Guru Prashanth Guruganesh, Sahil Singla

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations


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 a12 + δ 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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings
EditorsFriedrich Eisenbrand, Jochen Koenemann
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319592497
StatePublished - 2017
Event19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 - Waterloo, Canada
Duration: Jun 26 2017Jun 28 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10328 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Competitive analysis
  • Linear-time algorithms
  • Matroid intersection
  • Online algorithms
  • Randomized algorithms


Dive into the research topics of 'Online matroid intersection: Beating half for random arrival'. Together they form a unique fingerprint.

Cite this