Online matroid intersection: Beating half for random arrival

Guru Prashanth Guruganesh, Sahil Singla

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

9 Scopus citations

Abstract

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
Pages241-253
Number of pages13
ISBN (Print)9783319592497
DOIs
StatePublished - Jan 1 2017
Externally publishedYes
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

Other

Other19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017
CountryCanada
CityWaterloo
Period6/26/176/28/17

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

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

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

  • Cite this

    Guruganesh, G. P., & Singla, S. (2017). Online matroid intersection: Beating half for random arrival. In F. Eisenbrand, & J. Koenemann (Eds.), Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings (pp. 241-253). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10328 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-59250-3_20