On the max-cut of sparse random graphs
We consider the problem of estimating the size of a maximum cut (Max-Cut problem) in a random Erdős-Rényi graph on n nodes and ⌊cn⌋ edges. It is shown in Coppersmith et al. that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region [c/2 + 0.376...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Wiley
2019
|
| Online Access: | http://hdl.handle.net/1721.1/120495 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0002-3726-1517 |
| _version_ | 1826211115971903488 |
|---|---|
| author | Gamarnik, David Li, Quan |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Gamarnik, David Li, Quan |
| author_sort | Gamarnik, David |
| collection | MIT |
| description | We consider the problem of estimating the size of a maximum cut (Max-Cut problem) in a random Erdős-Rényi graph on n nodes and ⌊cn⌋ edges. It is shown in Coppersmith et al. that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region [c/2 + 0.37613√c, c/2 + 0.58870√c] with high probability (w.h.p.) as n increases, for all sufficiently large c. The upper bound was obtained by application of the first moment method, and the lower bound was obtained by constructing algorithmically a cut which achieves the stated lower bound. In this paper, we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval [c/2 + 0.47523√
c, c/2 + 0.55909√c] w.h.p. as n increases, for all sufficiently large c. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as c increases and use it to obtain an improved upper bound on the Max-Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value c/2+0.47523√c. It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of (Formula presented.) on the Max-Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of 1.33773n. |
| first_indexed | 2024-09-23T15:00:50Z |
| format | Article |
| id | mit-1721.1/120495 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:00:50Z |
| publishDate | 2019 |
| publisher | Wiley |
| record_format | dspace |
| spelling | mit-1721.1/1204952022-09-29T12:04:40Z On the max-cut of sparse random graphs Gamarnik, David Li, Quan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Sloan School of Management Gamarnik, David Li, Quan We consider the problem of estimating the size of a maximum cut (Max-Cut problem) in a random Erdős-Rényi graph on n nodes and ⌊cn⌋ edges. It is shown in Coppersmith et al. that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region [c/2 + 0.37613√c, c/2 + 0.58870√c] with high probability (w.h.p.) as n increases, for all sufficiently large c. The upper bound was obtained by application of the first moment method, and the lower bound was obtained by constructing algorithmically a cut which achieves the stated lower bound. In this paper, we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval [c/2 + 0.47523√ c, c/2 + 0.55909√c] w.h.p. as n increases, for all sufficiently large c. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as c increases and use it to obtain an improved upper bound on the Max-Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value c/2+0.47523√c. It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of (Formula presented.) on the Max-Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of 1.33773n. 2019-02-19T19:06:10Z 2019-02-19T19:06:10Z 2017-11 2019-02-13T17:46:33Z Article http://purl.org/eprint/type/JournalArticle 1042-9832 http://hdl.handle.net/1721.1/120495 Gamarnik, David, and Quan Li. “On the Max-Cut of Sparse Random Graphs.” Random Structures & Algorithms 52, no. 2 (November 13, 2017): 219–262. https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0002-3726-1517 http://dx.doi.org/10.1002/RSA.20738 Random Structures & Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Wiley arXiv |
| spellingShingle | Gamarnik, David Li, Quan On the max-cut of sparse random graphs |
| title | On the max-cut of sparse random graphs |
| title_full | On the max-cut of sparse random graphs |
| title_fullStr | On the max-cut of sparse random graphs |
| title_full_unstemmed | On the max-cut of sparse random graphs |
| title_short | On the max-cut of sparse random graphs |
| title_sort | on the max cut of sparse random graphs |
| url | http://hdl.handle.net/1721.1/120495 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0002-3726-1517 |
| work_keys_str_mv | AT gamarnikdavid onthemaxcutofsparserandomgraphs AT liquan onthemaxcutofsparserandomgraphs |