## Abstract

We study the problem of computing an approximate maximum cardinality matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, the edges of the input graph G = (V, E) are given as a stream e1, . . ., em, and the algorithm is allowed to make a single pass over this stream while using O(npolylog(n)) space (m = |E| and n = |V |). If the order of edges is adversarial, a simple single-pass greedy algorithm yields a 1/2-approximation in O(n) space; achieving a better approximation in adversarial streams remains an elusive open question. A line of recent work shows that one can improve upon the 1/2-approximation if the edges of the stream arrive in a random order. The state of the art for this model is two-fold: Assadi et al. [SODA 2019] show how to compute a ^{2}_{3} (∼ .66)-approximate matching, but the space requirement is O(n^{1.5}polylog(n)). Very recently, Farhadi et al. [SODA 2020] presented an algorithm with the desired space usage of O(npolylog(n)), but a worse approximation ratio of _{11}^{6} (∼ .545), or ^{3}_{5} (= .6) in bipartite graphs. In this paper, we present an algorithm that computes a ^{2}_{3} (∼ .66)-approximate matching using only O(n log(n)) space, improving upon both results above. We also note that for adversarial streams, a lower bound of Kapralov [SODA 2013] shows that any algorithm that achieves a 1 − ^{1}_{e} (∼ .63)-approximation requires (n^{1+Ω(1}/ log log(n^{))}) space. Our result for random-order streams is the first to go beyond the adversarial-order lower bound, thus establishing that computing a maximum matching is provably easier in random-order streams.

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

Title of host publication | 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 |

Editors | Artur Czumaj, Anuj Dawar, Emanuela Merelli |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771382 |

DOIs | |

State | Published - Jun 1 2020 |

Event | 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 - Virtual, Online, Germany Duration: Jul 8 2020 → Jul 11 2020 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 168 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 |
---|---|

Country/Territory | Germany |

City | Virtual, Online |

Period | 7/8/20 → 7/11/20 |

## Keywords

- Graph Algorithms
- Matching
- Streaming
- Sublinear Algorithms

## ASJC Scopus subject areas

- Software