A simple iterative algorithm for maxcut
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911962240122880 |
|---|---|
| author | Shao, Sihong Zhang, Dong Zhang, Weixi |
| author_facet | Shao, Sihong Zhang, Dong Zhang, Weixi |
| contents | We propose a simple iterative (SI) algorithm for the maxcut 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 cut values are monotonically updated and the iteration points converge to a local optima in finite steps via an appropriate subgradient selection. Numerical experiments on G-set demonstrate the performance. In particular, the ratios between the best cut values achieved by SI and those by some advanced combinatorial algorithms in [Ann. Oper. Res. 248 (2017) 365] are at least $0.986$ and can be further improved to at least $0.997$ by a preliminary attempt to break out of local optima. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1803_06496 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | A simple iterative algorithm for maxcut Shao, Sihong Zhang, Dong Zhang, Weixi Optimization and Control Numerical Analysis Combinatorics 90C27, 05C85, 65K10, 90C26, 90C32 We propose a simple iterative (SI) algorithm for the maxcut 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 cut values are monotonically updated and the iteration points converge to a local optima in finite steps via an appropriate subgradient selection. Numerical experiments on G-set demonstrate the performance. In particular, the ratios between the best cut values achieved by SI and those by some advanced combinatorial algorithms in [Ann. Oper. Res. 248 (2017) 365] are at least $0.986$ and can be further improved to at least $0.997$ by a preliminary attempt to break out of local optima. |
| title | A simple iterative algorithm for maxcut |
| topic | Optimization and Control Numerical Analysis Combinatorics 90C27, 05C85, 65K10, 90C26, 90C32 |
| url | https://arxiv.org/abs/1803.06496 |