|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
24 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Local Max-Cut on Sparse Graphs | | Gregory Schwartzman
; | | Date: |
1 Nov 2023 | | Abstract: | We bound the smoothed running time of the FLIP algorithm for local Max-Cut as a function of $alpha$, the arboricity of the input graph. We show that, with high probability, the following holds (where $n$ is the number of nodes and $phi$ is the smoothing parameter):
1) When $alpha = O(sqrt{log n})$ FLIP terminates in $phi poly(n)$ iterations. Previous to our results the only graph families for which FLIP was known to achieve a smoothed polynomial running time were complete graphs and graphs with logarithmic maximum degree.
2) For arbitrary values of $alpha$ we get a running time of $phi n^{O(frac{alpha}{log n} + log alpha)}$. This improves over the best known running time for general graphs of $phi n^{O(sqrt{ log n })}$ for $alpha = o(log^{1.5} n)$. Specifically, when $alpha = O(log n)$ we get a significantly faster running time of $phi n^{O(log log n)}$. | | Source: | arXiv, 2311.00182 | | 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.
|
| |
|
|
|
REGISTER