Speeding up a memetic algorithm   for the max-bisection problem

Wenxing  Zhu; Yanpo  Liu; Geng  Lin

doi:10.3934/naco.2015.5.151

Previous Article
A wedge trust region method with self-correcting geometry for derivative-free optimization
NACO Home
This Issue
Next Article
A perturbation-based approach for continuous network design problem with emissions

2015, 5(2): 151-168. doi: 10.3934/naco.2015.5.151

Speeding up a memetic algorithm for the max-bisection problem

Wenxing Zhu ^1, , Yanpo Liu ^1, and Geng Lin ^2,

1.	Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350108, China, China
2.	Department of Mathematics, Minjiang University, Fuzhou, 350108, China

Received September 2014 Revised May 2015 Published June 2015

Abstract
Related Papers

Max-bisection of a weighted graph $G = (V, E)$ is to partition the vertex set $V$ into two subsets that have equal cardinality, such that the sum of the weights of the edges connecting vertices in different subsets is maximized. It is an NP-complete problem. Various heuristics have been proposed for solving the max-bisection problem and some of them get very good quality solutions, but are time consuming. In this paper, we propose several techniques to speeding up Lin and Zhu's memetic algorithm for this problem. It consists of a crossover operator with a greedy strategy, a fast modified Kernighan-Lin local search, and a new population updating function. Experiments are performed on 71 well-known G-set benchmark instances. Results show that the memetic algorithm is much faster than Wu and Hao's memetic algorithm, which can get best solutions up to now, on middle-scale and large-scale instances. Specifically, some current best known solutions of the test instances are improved.

Keywords: local search., memetic algorithm, Max-bisection, crossover.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.

Citation: Wenxing Zhu, Yanpo Liu, Geng Lin. Speeding up a memetic algorithm for the max-bisection problem. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 151-168. doi: 10.3934/naco.2015.5.151

References:

[1]	C. Ashcraft and J. W. H. Liu, Using domain decomposition to find graph bisectors,, BIT Numerical Mathematics, 37 (1997), 506. doi: 10.1007/BF02510238. Google Scholar
[2]	P. Austrin, S. Benabbas and K. Georgiou, Better balance by being biased: a 0.8776-approximation for max bisection,, in Proceedings of SODA, (2013), 277. Google Scholar
[3]	F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design,, Operations Research, 36 (1988), 493. Google Scholar
[4]	R. Battiti and A. Bertossi, Differential greedy for the 0-1 equicut problem,, in Proceeding of the DIMACS Workshop on Network Design: Connectivity and Facilities Location* (eds. D. Z. Du and P. M. Pardalos)*, (1997). Google Scholar
[5]	L. Brunetta, M. Conforti and G. Rinaldi, A branch-and-cut algorithm for the equicut problem,, Mathematical Programming, 78 (1997), 243. doi: 10.1016/S0025-5610(97)00017-8. Google Scholar
[6]	K. C. Chang and D. H-C. Du, Efficient algorithms for layer assignment problems,, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6 (1987), 67. Google Scholar
[7]	P. Chardaire, M. Barake and G. P. McKeown, A PROBE-based heuristic for graph partitioning,, IEEE Transactions on Computers, 56 (2007), 1707. doi: 10.1109/TC.2007.70760. Google Scholar
[8]	R. K. F. Chung, Spectral Graph Theory,, 92, (1997). Google Scholar
[9]	C. Dang, L. He and I. K. Hui, A deterministic annealing algorithm for approximating a solution of the max-bisection problem,, Neural Networks, 15 (2002), 441. Google Scholar
[10]	A. Duarte, F. Fernández, Á. Sánchez and A. Sanz, A hierarchical social metaheuristic for the max-cut problem,, Lecture Notes in computer Science, 3004 (2004), 84. Google Scholar
[11]	U. Feige, M. Karpinski and M. Langberg, A note on approximating max-bisection on regular graphs,, \emph{Information Processing Letters}, 79 (2001), 181. doi: 10.1016/S0020-0190(00)00189-7. Google Scholar
[12]	C. M. Fiduccia and R. M. Mattheyses, A linear time heuristic for improving network partitions,, in Proceedings of the 19th Design Automation Conference, (1982), 175. Google Scholar
[13]	A. Frieze and M. Jerrum, Improved approximation algorithm for max k-cut and max-bisection,, Algorithmica, 18 (1997), 67. doi: 10.1007/BF02523688. Google Scholar
[14]	M. X. Goemans and D. P. Williamson, Improved approximation algorithms for Max-Cut and satisfiability problems using semidefinite programming,, Journal of the ACM, 42 (1995), 1115. doi: 10.1145/227683.227684. Google Scholar
[15]	E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems,, Random Structures and Algorithms, 20 (2002), 382. doi: 10.1002/rsa.10035. Google Scholar
[16]	J. Hastad, Some optimal inapproachability results,, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, (1997), 1. Google Scholar
[17]	C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming,, SIAM Journal on Optimization, 10 (2000), 673. doi: 10.1137/S1052623497328987. Google Scholar
[18]	B. Hendrickson and R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations,, SIAM Journal on Scientific Computing, 16 (1995), 452. doi: 10.1137/0916028. Google Scholar
[19]	J. H. Holland, Adaptation in Natural Artificial System,, The University of Michigan Press (Second edition; MIT press), (1992). Google Scholar
[20]	K. Jansen, M. Karpinski, A. Lingas and E. Seidel, Polynomial time approximation schemes for Max-Bisection on planar and geometric graphs,, SIAM Journal on Computing, 35 (2005), 110. doi: 10.1137/S009753970139567X. Google Scholar
[21]	R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations* (eds. R. E. Miller and J. W. Thatcher)*, (1972), 85. Google Scholar
[22]	M. Karpinski, M. Kowaluk and A. Lingas, Approximation algorithms for MAX-BISECTION on low degree regular graphs,, Fundamenta Informaticae, 62 (2004), 369. Google Scholar
[23]	B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs,, The Bell System Technical Journal, 49 (1970), 291. Google Scholar
[24]	S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs,, SIAM Journal on Computing, 37 (2007), 319. doi: 10.1137/S0097539705447372. Google Scholar
[25]	D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming,, Vol. 2, (1997). Google Scholar
[26]	K. Krishnan and J. Mitchell, A semidefinite programming based polyhedral cut and price approach for the Max-Cut problem,, Computational Optimization and Applications, 33 (2006), 51. doi: 10.1007/s10589-005-5958-3. Google Scholar
[27]	R. B. Lin and S. Y. Chen, Conjugate conflict continuation graphs for multilayer constrained via minimization,, Information Sciences, 177 (2007), 2436. doi: 10.1016/j.ins.2007.01.013. Google Scholar
[28]	G. Lin and W. Zhu, An efficient memetic algorithm for solving the Max-Bisection problem,, IEEE Transactions on Computers, 63 (2014), 1365. doi: 10.1109/TC.2013.7. Google Scholar
[29]	A. F. Ling, C. X. Xu and L. Tang, A modified VNS metaheuristic for max-bisection problems,, Journal of Computational and Applied Mathematics, 220 (2008), 413. doi: 10.1016/j.cam.2007.08.018. Google Scholar
[30]	R. Marti, A. Duarte and M. Laguna, Advanced scatter search for the max-cut problem,, INFORMS Journal on Computing, 21 (2009), 26. doi: 10.1287/ijoc.1080.0275. Google Scholar
[31]	P. Moscato and C. Cotta, A gentle introduction to memetic algorithms,, in Handbook of Metaheuristics* (eds. F. Glover and G. A. Kochenberger)*, (2003). doi: 10.1007/0-306-48056-5_5. Google Scholar
[32]	K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming,, Mathematical Programming, 39 (1987), 117. doi: 10.1007/BF02592948. Google Scholar
[33]	F. Neri, C. Cotta and P. Moscato, Handbook of Memetic Algorithms,, Studies in Computational Intelligence, (2011). doi: 10.1007/978-3-642-23247-3. Google Scholar
[34]	G. Palubeckis and V. Krivickiene, Application of multistart tabu search to the Max Cut problem,, Information Technology and Control, 2 (2004), 29. Google Scholar
[35]	P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies,, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, (2012), 373. Google Scholar
[36]	V. P. Shylo and O. V. Shylo, Solving the max-cut problem by the global equilibrium search,, Cybernetics and Systems Analysis, 46 (2010), 744. Google Scholar
[37]	K. Sörensen and M. Sevaux, MA\|PM: memetic algorithms with population management,, Computers and Operations Research, 33 (2006), 1214. Google Scholar
[38]	C. C. de Souza, R. Keunings, L. A. Wolsey and O. Zone, A new approach to minimizing the front width in finite element calculations,, Computer Methods in Applied Mechanics and Engineering, 111 (1994), 323. doi: 10.1016/0045-7825(94)90137-6. Google Scholar
[39]	D. Spielman, Spectral Graph Theory,, Lecture Notes, (2009). Google Scholar
[40]	E. W. Weisstein, Laplacian Matrix,, MathWorld-A Wolfram Web Resource, (1995). Google Scholar
[41]	Q. Wu and J. K. Hao, Memetic search for the max-bisection problem,, Computers and Operations Research, 40 (2013), 166. doi: 10.1016/j.cor.2012.06.001. Google Scholar
[42]	F. Xu, X. Ma and B. Chen, A new Lagrangian net algorithm for solving max-bisection problems,, Journal of Computational and Applied Mathematics, 235 (2011), 3718. doi: 10.1016/j.cam.2011.01.015. Google Scholar
[43]	Y. Y. Ye, A 0.699-approximation algorithm for Max-Bisection,, Mathematical Programming, 90 (2001), 101. doi: 10.1007/PL00011415. Google Scholar

show all references

References:

[1]	C. Ashcraft and J. W. H. Liu, Using domain decomposition to find graph bisectors,, BIT Numerical Mathematics, 37 (1997), 506. doi: 10.1007/BF02510238. Google Scholar
[2]	P. Austrin, S. Benabbas and K. Georgiou, Better balance by being biased: a 0.8776-approximation for max bisection,, in Proceedings of SODA, (2013), 277. Google Scholar
[3]	F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design,, Operations Research, 36 (1988), 493. Google Scholar
[4]	R. Battiti and A. Bertossi, Differential greedy for the 0-1 equicut problem,, in Proceeding of the DIMACS Workshop on Network Design: Connectivity and Facilities Location* (eds. D. Z. Du and P. M. Pardalos)*, (1997). Google Scholar
[5]	L. Brunetta, M. Conforti and G. Rinaldi, A branch-and-cut algorithm for the equicut problem,, Mathematical Programming, 78 (1997), 243. doi: 10.1016/S0025-5610(97)00017-8. Google Scholar
[6]	K. C. Chang and D. H-C. Du, Efficient algorithms for layer assignment problems,, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6 (1987), 67. Google Scholar
[7]	P. Chardaire, M. Barake and G. P. McKeown, A PROBE-based heuristic for graph partitioning,, IEEE Transactions on Computers, 56 (2007), 1707. doi: 10.1109/TC.2007.70760. Google Scholar
[8]	R. K. F. Chung, Spectral Graph Theory,, 92, (1997). Google Scholar
[9]	C. Dang, L. He and I. K. Hui, A deterministic annealing algorithm for approximating a solution of the max-bisection problem,, Neural Networks, 15 (2002), 441. Google Scholar
[10]	A. Duarte, F. Fernández, Á. Sánchez and A. Sanz, A hierarchical social metaheuristic for the max-cut problem,, Lecture Notes in computer Science, 3004 (2004), 84. Google Scholar
[11]	U. Feige, M. Karpinski and M. Langberg, A note on approximating max-bisection on regular graphs,, \emph{Information Processing Letters}, 79 (2001), 181. doi: 10.1016/S0020-0190(00)00189-7. Google Scholar
[12]	C. M. Fiduccia and R. M. Mattheyses, A linear time heuristic for improving network partitions,, in Proceedings of the 19th Design Automation Conference, (1982), 175. Google Scholar
[13]	A. Frieze and M. Jerrum, Improved approximation algorithm for max k-cut and max-bisection,, Algorithmica, 18 (1997), 67. doi: 10.1007/BF02523688. Google Scholar
[14]	M. X. Goemans and D. P. Williamson, Improved approximation algorithms for Max-Cut and satisfiability problems using semidefinite programming,, Journal of the ACM, 42 (1995), 1115. doi: 10.1145/227683.227684. Google Scholar
[15]	E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems,, Random Structures and Algorithms, 20 (2002), 382. doi: 10.1002/rsa.10035. Google Scholar
[16]	J. Hastad, Some optimal inapproachability results,, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, (1997), 1. Google Scholar
[17]	C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming,, SIAM Journal on Optimization, 10 (2000), 673. doi: 10.1137/S1052623497328987. Google Scholar
[18]	B. Hendrickson and R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations,, SIAM Journal on Scientific Computing, 16 (1995), 452. doi: 10.1137/0916028. Google Scholar
[19]	J. H. Holland, Adaptation in Natural Artificial System,, The University of Michigan Press (Second edition; MIT press), (1992). Google Scholar
[20]	K. Jansen, M. Karpinski, A. Lingas and E. Seidel, Polynomial time approximation schemes for Max-Bisection on planar and geometric graphs,, SIAM Journal on Computing, 35 (2005), 110. doi: 10.1137/S009753970139567X. Google Scholar
[21]	R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations* (eds. R. E. Miller and J. W. Thatcher)*, (1972), 85. Google Scholar
[22]	M. Karpinski, M. Kowaluk and A. Lingas, Approximation algorithms for MAX-BISECTION on low degree regular graphs,, Fundamenta Informaticae, 62 (2004), 369. Google Scholar
[23]	B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs,, The Bell System Technical Journal, 49 (1970), 291. Google Scholar
[24]	S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs,, SIAM Journal on Computing, 37 (2007), 319. doi: 10.1137/S0097539705447372. Google Scholar
[25]	D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming,, Vol. 2, (1997). Google Scholar
[26]	K. Krishnan and J. Mitchell, A semidefinite programming based polyhedral cut and price approach for the Max-Cut problem,, Computational Optimization and Applications, 33 (2006), 51. doi: 10.1007/s10589-005-5958-3. Google Scholar
[27]	R. B. Lin and S. Y. Chen, Conjugate conflict continuation graphs for multilayer constrained via minimization,, Information Sciences, 177 (2007), 2436. doi: 10.1016/j.ins.2007.01.013. Google Scholar
[28]	G. Lin and W. Zhu, An efficient memetic algorithm for solving the Max-Bisection problem,, IEEE Transactions on Computers, 63 (2014), 1365. doi: 10.1109/TC.2013.7. Google Scholar
[29]	A. F. Ling, C. X. Xu and L. Tang, A modified VNS metaheuristic for max-bisection problems,, Journal of Computational and Applied Mathematics, 220 (2008), 413. doi: 10.1016/j.cam.2007.08.018. Google Scholar
[30]	R. Marti, A. Duarte and M. Laguna, Advanced scatter search for the max-cut problem,, INFORMS Journal on Computing, 21 (2009), 26. doi: 10.1287/ijoc.1080.0275. Google Scholar
[31]	P. Moscato and C. Cotta, A gentle introduction to memetic algorithms,, in Handbook of Metaheuristics* (eds. F. Glover and G. A. Kochenberger)*, (2003). doi: 10.1007/0-306-48056-5_5. Google Scholar
[32]	K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming,, Mathematical Programming, 39 (1987), 117. doi: 10.1007/BF02592948. Google Scholar
[33]	F. Neri, C. Cotta and P. Moscato, Handbook of Memetic Algorithms,, Studies in Computational Intelligence, (2011). doi: 10.1007/978-3-642-23247-3. Google Scholar
[34]	G. Palubeckis and V. Krivickiene, Application of multistart tabu search to the Max Cut problem,, Information Technology and Control, 2 (2004), 29. Google Scholar
[35]	P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies,, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, (2012), 373. Google Scholar
[36]	V. P. Shylo and O. V. Shylo, Solving the max-cut problem by the global equilibrium search,, Cybernetics and Systems Analysis, 46 (2010), 744. Google Scholar
[37]	K. Sörensen and M. Sevaux, MA\|PM: memetic algorithms with population management,, Computers and Operations Research, 33 (2006), 1214. Google Scholar
[38]	C. C. de Souza, R. Keunings, L. A. Wolsey and O. Zone, A new approach to minimizing the front width in finite element calculations,, Computer Methods in Applied Mechanics and Engineering, 111 (1994), 323. doi: 10.1016/0045-7825(94)90137-6. Google Scholar
[39]	D. Spielman, Spectral Graph Theory,, Lecture Notes, (2009). Google Scholar
[40]	E. W. Weisstein, Laplacian Matrix,, MathWorld-A Wolfram Web Resource, (1995). Google Scholar
[41]	Q. Wu and J. K. Hao, Memetic search for the max-bisection problem,, Computers and Operations Research, 40 (2013), 166. doi: 10.1016/j.cor.2012.06.001. Google Scholar
[42]	F. Xu, X. Ma and B. Chen, A new Lagrangian net algorithm for solving max-bisection problems,, Journal of Computational and Applied Mathematics, 235 (2011), 3718. doi: 10.1016/j.cam.2011.01.015. Google Scholar
[43]	Y. Y. Ye, A 0.699-approximation algorithm for Max-Bisection,, Mathematical Programming, 90 (2001), 101. doi: 10.1007/PL00011415. Google Scholar

[1]	Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041
[2]	Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020056
[3]	Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[4]	Dieudonné Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique. Tabu search guided by reinforcement learning for the max-mean dispersion problem. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020115
[5]	Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142
[6]	Baolan Yuan, Wanjun Zhang, Yubo Yuan. A Max-Min clustering method for $k$-means algorithm of data clustering. Journal of Industrial & Management Optimization, 2012, 8 (3) : 565-575. doi: 10.3934/jimo.2012.8.565
[7]	Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193
[8]	Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[9]	Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017
[10]	Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11
[11]	Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020045
[12]	Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191
[13]	Sen Zhang, Guo Zhou, Yongquan Zhou, Qifang Luo. Quantum-inspired satin bowerbird algorithm with Bloch spherical search for constrained structural optimization. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020130
[14]	Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703
[15]	Leong-Kwan Li, Sally Shao, K. F. Cedric Yiu. Nonlinear dynamical system modeling via recurrent neural networks and a weighted state space search algorithm. Journal of Industrial & Management Optimization, 2011, 7 (2) : 385-400. doi: 10.3934/jimo.2011.7.385
[16]	Yunsai Chen, Zhao Yang, Liang Ma, Peng Li, Yongjie Pang, Xin Zhao, Wenyi Yang. Efficient extraction algorithm for local fuzzy features of dynamic images. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1311-1325. doi: 10.3934/dcdss.2019090
[17]	Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial & Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31
[18]	José M. Amigó, Ángel Giménez. Formulas for the topological entropy of multimodal maps based on min-max symbols. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3415-3434. doi: 10.3934/dcdsb.2015.20.3415
[19]	X. X. Huang, Xiaoqi Yang, K. L. Teo. A smoothing scheme for optimization problems with Max-Min constraints. Journal of Industrial & Management Optimization, 2007, 3 (2) : 209-222. doi: 10.3934/jimo.2007.3.209
[20]	Blaine Keetch, Yves van Gennip. A Max-Cut approximation using a graph based MBO scheme. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 6091-6139. doi: 10.3934/dcdsb.2019132

Impact Factor:

American Institute of Mathematical Sciences

Speeding up a memetic algorithm for the max-bisection problem

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Speeding up a memetic algorithm for the max-bisection problem

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors