-
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] |
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:
Tools
Metrics
Other articles
by authors
[Back to Top]