Continuous iterative algorithms for anti-Cheeger cut
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929704087322624 |
|---|---|
| author | Shao, Sihong Yang, Chuan |
| author_facet | Shao, Sihong Yang, Chuan |
| contents | As a judicious correspondence to the classical maxcut, the anti-Cheeger cut has more balanced structure, but few numerical results on it have been reported so far. In this paper, we propose a continuous iterative algorithm (CIA) for the anti-Cheeger cut problem through fully using an equivalent continuous formulation. It does not need rounding at all and has advantages that all subproblems have explicit analytic solutions, the objective function values are monotonically updated and the iteration points converge to a local optimum in finite steps via an appropriate subgradient selection. It can also be easily combined with the maxcut iterations for breaking out of local optima and improving the solution quality thanks to the similarity between the anti-Cheeger cut problem and the maxcut problem. The performance of CIAs is fully demonstrated through numerical experiments on G-set from two aspects: one is on the solution quality where we find that the approximate solutions obtained by CIAs are of comparable quality to those by the multiple search operator heuristic method; the other is on the computational cost where we show that CIAs always run faster than the often-used continuous iterative algorithm based on the rank-two relaxation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_10705 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Continuous iterative algorithms for anti-Cheeger cut Shao, Sihong Yang, Chuan Optimization and Control Numerical Analysis Combinatorics 90C27, 05C85, 65K10, 90C26, 90C32 As a judicious correspondence to the classical maxcut, the anti-Cheeger cut has more balanced structure, but few numerical results on it have been reported so far. In this paper, we propose a continuous iterative algorithm (CIA) for the anti-Cheeger cut problem through fully using an equivalent continuous formulation. It does not need rounding at all and has advantages that all subproblems have explicit analytic solutions, the objective function values are monotonically updated and the iteration points converge to a local optimum in finite steps via an appropriate subgradient selection. It can also be easily combined with the maxcut iterations for breaking out of local optima and improving the solution quality thanks to the similarity between the anti-Cheeger cut problem and the maxcut problem. The performance of CIAs is fully demonstrated through numerical experiments on G-set from two aspects: one is on the solution quality where we find that the approximate solutions obtained by CIAs are of comparable quality to those by the multiple search operator heuristic method; the other is on the computational cost where we show that CIAs always run faster than the often-used continuous iterative algorithm based on the rank-two relaxation. |
| title | Continuous iterative algorithms for anti-Cheeger cut |
| topic | Optimization and Control Numerical Analysis Combinatorics 90C27, 05C85, 65K10, 90C26, 90C32 |
| url | https://arxiv.org/abs/2103.10705 |