Online matroid intersection: Beating half for random arrival

Guru Prashanth Guruganesh, Sahil Singla

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

13 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