Sketching Cuts in Graphs and Hypergraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2014
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912913820745728 |
|---|---|
| author | Kogan, Dmitry Krauthgamer, Robert |
| author_facet | Kogan, Dmitry Krauthgamer, Robert |
| contents | Sketching and streaming algorithms are in the forefront of current research directions for cut problems in graphs. In the streaming model, we show that $(1-ε)$-approximation for Max-Cut must use $n^{1-O(ε)}$ space; moreover, beating $4/5$-approximation requires polynomial space. For the sketching model, we show that $r$-uniform hypergraphs admit a $(1+ε)$-cut-sparsifier (i.e., a weighted subhypergraph that approximately preserves all the cuts) with $O(ε^{-2} n (r+\log n))$ edges. We also make first steps towards sketching general CSPs (Constraint Satisfaction Problems). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1409_2391 |
| institution | arXiv |
| publishDate | 2014 |
| record_format | arxiv |
| spellingShingle | Sketching Cuts in Graphs and Hypergraphs Kogan, Dmitry Krauthgamer, Robert Data Structures and Algorithms Sketching and streaming algorithms are in the forefront of current research directions for cut problems in graphs. In the streaming model, we show that $(1-ε)$-approximation for Max-Cut must use $n^{1-O(ε)}$ space; moreover, beating $4/5$-approximation requires polynomial space. For the sketching model, we show that $r$-uniform hypergraphs admit a $(1+ε)$-cut-sparsifier (i.e., a weighted subhypergraph that approximately preserves all the cuts) with $O(ε^{-2} n (r+\log n))$ edges. We also make first steps towards sketching general CSPs (Constraint Satisfaction Problems). |
| title | Sketching Cuts in Graphs and Hypergraphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/1409.2391 |