Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings
We prove that any semi-streaming algorithm for $(1-ε)$-approximation of maximum bipartite matching requires \[ Ω(\frac{\log{(1/ε)}}{\log{(1/β)}}) \] passes, where $β\in (0,1)$ is the largest parameter so that an $n$-vertex graph with $n^β$ edge-disjoint induced matchings of size $Θ(n)$ exist (such g...
Gardado en:
| Autores principales: | , |
|---|---|
| Formato: | Artigo |
| Publicado: |
2023
|
| Materias: | |
| Acceso en liña: | https://arxiv.org/abs/2310.05728 http://arxiv.org/abs/2310.05728 |
| Etiquetas: |
Sen Etiquetas, Sexa o primeiro en etiquetar este rexistro!
|