-
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
Speeding up a memetic algorithm for the max-bisection problem
1. | Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350108, China, China |
2. | Department of Mathematics, Minjiang University, Fuzhou, 350108, China |
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. |
[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.
|
[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).
|
[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. |
[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. |
[8] |
R. K. F. Chung, Spectral Graph Theory,, 92, (1997).
|
[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. |
[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. |
[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. |
[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. |
[16] |
J. Hastad, Some optimal inapproachability results,, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, (1997), 1.
|
[17] |
C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming,, SIAM Journal on Optimization, 10 (2000), 673.
doi: 10.1137/S1052623497328987. |
[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. |
[19] |
J. H. Holland, Adaptation in Natural Artificial System,, The University of Michigan Press (Second edition; MIT press), (1992).
|
[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. |
[21] |
R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations (eds. R. E. Miller and J. W. Thatcher), (1972), 85.
|
[22] |
M. Karpinski, M. Kowaluk and A. Lingas, Approximation algorithms for MAX-BISECTION on low degree regular graphs,, Fundamenta Informaticae, 62 (2004), 369.
|
[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. |
[25] |
D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming,, Vol. 2, (1997).
|
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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.
|
[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. |
[39] |
D. Spielman, Spectral Graph Theory,, Lecture Notes, (2009).
|
[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. |
[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. |
[43] |
Y. Y. Ye, A 0.699-approximation algorithm for Max-Bisection,, Mathematical Programming, 90 (2001), 101.
doi: 10.1007/PL00011415. |
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. |
[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.
|
[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).
|
[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. |
[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. |
[8] |
R. K. F. Chung, Spectral Graph Theory,, 92, (1997).
|
[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. |
[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. |
[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. |
[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. |
[16] |
J. Hastad, Some optimal inapproachability results,, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, (1997), 1.
|
[17] |
C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming,, SIAM Journal on Optimization, 10 (2000), 673.
doi: 10.1137/S1052623497328987. |
[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. |
[19] |
J. H. Holland, Adaptation in Natural Artificial System,, The University of Michigan Press (Second edition; MIT press), (1992).
|
[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. |
[21] |
R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations (eds. R. E. Miller and J. W. Thatcher), (1972), 85.
|
[22] |
M. Karpinski, M. Kowaluk and A. Lingas, Approximation algorithms for MAX-BISECTION on low degree regular graphs,, Fundamenta Informaticae, 62 (2004), 369.
|
[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. |
[25] |
D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming,, Vol. 2, (1997).
|
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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.
|
[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. |
[39] |
D. Spielman, Spectral Graph Theory,, Lecture Notes, (2009).
|
[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. |
[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. |
[43] |
Y. Y. Ye, A 0.699-approximation algorithm for Max-Bisection,, Mathematical Programming, 90 (2001), 101.
doi: 10.1007/PL00011415. |
[1] |
Qiao Liu. Local rigidity of certain solvable group actions on tori. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 553-567. doi: 10.3934/dcds.2020269 |
[2] |
Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 |
[3] |
M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014 |
[4] |
Editorial Office. Retraction: Jinling Wei, Jinming Zhang, Meishuang Dong, Fan Zhang, Yunmo Chen, Sha Jin and Zhike Han, Applications of mathematics to maritime search. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 957-957. doi: 10.3934/dcdss.2019064 |
[5] |
Thierry Cazenave, Ivan Naumkin. Local smooth solutions of the nonlinear Klein-gordon equation. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020448 |
[6] |
Roland Schnaubelt, Martin Spitz. Local wellposedness of quasilinear Maxwell equations with absorbing boundary conditions. Evolution Equations & Control Theory, 2021, 10 (1) : 155-198. doi: 10.3934/eect.2020061 |
[7] |
Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048 |
[8] |
Claudio Bonanno, Marco Lenci. Pomeau-Manneville maps are global-local mixing. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1051-1069. doi: 10.3934/dcds.2020309 |
[9] |
Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020319 |
[10] |
Xavier Carvajal, Liliana Esquivel, Raphael Santos. On local well-posedness and ill-posedness results for a coupled system of mkdv type equations. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020382 |
[11] |
Tong Tang, Jianzhu Sun. Local well-posedness for the density-dependent incompressible magneto-micropolar system with vacuum. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020377 |
[12] |
Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 |
[13] |
Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107 |
[14] |
Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060 |
[15] |
Editorial Office. Retraction: Xiaohong Zhu, Zili Yang and Tabharit Zoubir, Research on the matching algorithm for heterologous image after deformation in the same scene. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1281-1281. doi: 10.3934/dcdss.2019088 |
[16] |
Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 |
[17] |
Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122 |
[18] |
Editorial Office. Retraction: Xiaohong Zhu, Lihe Zhou, Zili Yang and Joyati Debnath, A new text information extraction algorithm of video image under multimedia environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1265-1265. doi: 10.3934/dcdss.2019087 |
[19] |
Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]