### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings |

Editors | Friedrich Eisenbrand, Jochen Koenemann |

Publisher | Springer Verlag |

Pages | 241-253 |

Number of pages | 13 |

ISBN (Print) | 9783319592497 |

DOIs | |

State | Published - Jan 1 2017 |

Externally published | Yes |

Event | 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 - Waterloo, Canada Duration: Jun 26 2017 → Jun 28 2017 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10328 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 |
---|---|

Country | Canada |

City | Waterloo |

Period | 6/26/17 → 6/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

*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