Dual Cheeger Constants, Signless 1-Laplacians and Maxcut
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2016
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909461344419840 |
|---|---|
| author | Shao, Sihong Yang, Chuan Zhang, Dong |
| author_facet | Shao, Sihong Yang, Chuan Zhang, Dong |
| contents | The first nontrivial lower bound of the worst-case approximation ratio for the maxcut problem was achieved via the dual Cheeger problem, whose optimal value is referred to the dual Cheeger constant $h^+$, and later improved through its modification $\widehat{h}^+$. However, the dual Cheeger problem and its modification themselves are relatively unexplored, especially lack of effective approximate algorithms. To this end, we first derive equivalent spectral formulations of $h^+$ and $\widehat{h}^+$ within the framework of the nonlinear spectral theory of signless 1-Laplacian, present their interactions with the Laplacian matrix and 1-Laplacian, and then use them to develop an inverse power algorithm that leverages the local linearity of the objective functions involved. We prove that the inverse power algorithm monotonically converges to a ternary-valued eigenvector, and provide the approximate values of $h^+$ and $\widehat{h}^+$ on G-set for the first time. The recursive spectral cut algorithm for the maxcut problem can be enhanced by integrating into the inverse power algorithms, leading to significantly improved approximate values on G-set. Finally, we show that the lower bound of the worst-case approximation ratio for the maxcut problem within the recursive spectral cut framework can not be improved beyond $0.769$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1607_00489 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | Dual Cheeger Constants, Signless 1-Laplacians and Maxcut Shao, Sihong Yang, Chuan Zhang, Dong Spectral Theory Combinatorics Optimization and Control 05C85, 90C27, 58C40, 35P30, 05C50 The first nontrivial lower bound of the worst-case approximation ratio for the maxcut problem was achieved via the dual Cheeger problem, whose optimal value is referred to the dual Cheeger constant $h^+$, and later improved through its modification $\widehat{h}^+$. However, the dual Cheeger problem and its modification themselves are relatively unexplored, especially lack of effective approximate algorithms. To this end, we first derive equivalent spectral formulations of $h^+$ and $\widehat{h}^+$ within the framework of the nonlinear spectral theory of signless 1-Laplacian, present their interactions with the Laplacian matrix and 1-Laplacian, and then use them to develop an inverse power algorithm that leverages the local linearity of the objective functions involved. We prove that the inverse power algorithm monotonically converges to a ternary-valued eigenvector, and provide the approximate values of $h^+$ and $\widehat{h}^+$ on G-set for the first time. The recursive spectral cut algorithm for the maxcut problem can be enhanced by integrating into the inverse power algorithms, leading to significantly improved approximate values on G-set. Finally, we show that the lower bound of the worst-case approximation ratio for the maxcut problem within the recursive spectral cut framework can not be improved beyond $0.769$. |
| title | Dual Cheeger Constants, Signless 1-Laplacians and Maxcut |
| topic | Spectral Theory Combinatorics Optimization and Control 05C85, 90C27, 58C40, 35P30, 05C50 |
| url | https://arxiv.org/abs/1607.00489 |