File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/2330163.2330224
- Scopus: eid_2-s2.0-84864683921
- WOS: WOS:000309611100054
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: A hybridization between memetic algorithm and semidefinite relaxation for the max-cut problem
Title | A hybridization between memetic algorithm and semidefinite relaxation for the max-cut problem |
---|---|
Authors | |
Keywords | Hybrid algorithms Max-cut Memetic algorithm Semidefinite programming Bench-mark problems |
Issue Date | 2012 |
Publisher | Association for Computing Machinery. |
Citation | The 14th International Conference on Genetic and Evolutionary Computation (GECCO'12), Philadelphia, PA, 7-11 July 2012. In Proceedings of the 14th GECCO, 2012, p. 425-432 How to Cite? |
Abstract | The Max-Cut problem is a classical NP-hard combinatorial optimization problem. It consists of dividing the vertices of a weighted graph into two subsets, such that the sum of the weights of the edges connecting the two subsets is maximized. Although semidefinite relaxation algorithms for Max-Cut have been proved to be of high quality and offer performance guarantees, in practice, metaheuristic algorithms are still the first option to solve large Max-Cut instances. In this paper, we present the first effort at combining semidefinite programming (SDP) with metaheuristic algorithm (Memetic Algorithm) to solve the Max-Cut problem. Based on the solution of semidefinite relaxation, we use Goemans-Williamson Algorithm to seed high quality solutions to the initial population for the memetic algorithm. Experimental results on well-known benchmark problems show that our new hybrid algorithm is capable of obtaining better solutions in the initial population generation stage than previous algorithms, and the overall performance of our algorithm is better than one of the best existing algorithms. Besides, new best solutions for 14 benchmark problems were found by our algorithm. © 2012 ACM. |
Persistent Identifier | http://hdl.handle.net/10722/165277 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Song, B | en_US |
dc.contributor.author | Li, VOK | en_US |
dc.date.accessioned | 2012-09-20T08:16:37Z | - |
dc.date.available | 2012-09-20T08:16:37Z | - |
dc.date.issued | 2012 | en_US |
dc.identifier.citation | The 14th International Conference on Genetic and Evolutionary Computation (GECCO'12), Philadelphia, PA, 7-11 July 2012. In Proceedings of the 14th GECCO, 2012, p. 425-432 | en_US |
dc.identifier.isbn | 978-1-4503-1177-9 | - |
dc.identifier.uri | http://hdl.handle.net/10722/165277 | - |
dc.description.abstract | The Max-Cut problem is a classical NP-hard combinatorial optimization problem. It consists of dividing the vertices of a weighted graph into two subsets, such that the sum of the weights of the edges connecting the two subsets is maximized. Although semidefinite relaxation algorithms for Max-Cut have been proved to be of high quality and offer performance guarantees, in practice, metaheuristic algorithms are still the first option to solve large Max-Cut instances. In this paper, we present the first effort at combining semidefinite programming (SDP) with metaheuristic algorithm (Memetic Algorithm) to solve the Max-Cut problem. Based on the solution of semidefinite relaxation, we use Goemans-Williamson Algorithm to seed high quality solutions to the initial population for the memetic algorithm. Experimental results on well-known benchmark problems show that our new hybrid algorithm is capable of obtaining better solutions in the initial population generation stage than previous algorithms, and the overall performance of our algorithm is better than one of the best existing algorithms. Besides, new best solutions for 14 benchmark problems were found by our algorithm. © 2012 ACM. | - |
dc.language | eng | en_US |
dc.publisher | Association for Computing Machinery. | - |
dc.relation.ispartof | Proceedings of the 14th International Conference on Genetic and Evolutionary Computation, GECCO'12 | en_US |
dc.rights | Proceedings of the 14th International Conference on Genetic and Evolutionary Computation, GECCO'12. Copyright © Association for Computing Machinery. | - |
dc.subject | Hybrid algorithms | - |
dc.subject | Max-cut | - |
dc.subject | Memetic algorithm | - |
dc.subject | Semidefinite programming | - |
dc.subject | Bench-mark problems | - |
dc.title | A hybridization between memetic algorithm and semidefinite relaxation for the max-cut problem | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=978-1-4503-1177-9&volume=&spage=425&epage=432&date=2011&atitle=A+Hybridization+between+Memetic+Algorithm+and+Semidefinite+Relaxation+for+the+Max-Cut+Problem | en_US |
dc.identifier.email | Song, B: bsong@hku.hk | en_US |
dc.identifier.email | Li, VOK: vli@eee.hku.hk | - |
dc.identifier.authority | Li, VOK=rp00150 | en_US |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1145/2330163.2330224 | - |
dc.identifier.scopus | eid_2-s2.0-84864683921 | - |
dc.identifier.hkuros | 209597 | en_US |
dc.identifier.hkuros | 225563 | - |
dc.identifier.spage | 425 | en_US |
dc.identifier.epage | 432 | en_US |
dc.identifier.isi | WOS:000309611100054 | - |
dc.publisher.place | United States | - |
dc.description.other | The 14th International Conference on Genetic and Evolutionary Computation (GECCO'12), Philadelphia, PA, 7-11 July 2012. In Proceedings of the 14th GECCO, 2012, p. 425-432 | - |