Beating Two-Thirds For Random-Order Streaming Matching
We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary $n$-vertex graph $G=(V, E)$ arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use $n \cdot poly(\log n)$ space, and outpu...
Guardat en:
| Autors principals: | , |
|---|---|
| Format: | Article |
| Publicat: |
2021
|
| Matèries: | |
| Accés en línia: | https://arxiv.org/abs/2102.07011 http://arxiv.org/abs/2102.07011 |
| Etiquetes: |
Sense etiquetes, Sigues el primer a etiquetar aquest registre!
|