| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Towards a better approximation for sparsest cut? | Sanjeev Arora
; Rong Ge
; Ali Kemal Sinop
; | Date: |
11 Apr 2013 | Abstract: | We give a new $(1+epsilon)$-approximation for sparsest cut problem on graphs
where small sets expand significantly more than the sparsest cut (sets of size
$n/r$ expand by a factor $sqrt{log nlog r}$ bigger, for some small $r$; this
condition holds for many natural graph families). We give two different
algorithms. One involves Guruswami-Sinop rounding on the level-$r$ Lasserre
relaxation. The other is combinatorial and involves a new notion called {em
Small Set Expander Flows} (inspired by the {em expander flows} of ARV) which
we show exists in the input graph. Both algorithms run in time $2^{O(r)}
mathrm{poly}(n)$. We also show similar approximation algorithms in graphs with
genus $g$ with an analogous local expansion condition. This is the first
algorithm we know of that achieves $(1+epsilon)$-approximation on such general
family of graphs. | Source: | arXiv, 1304.3365 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |