zbMATH — the first resource for mathematics

A modified VNS metaheuristic for max-bisection problems. (English) Zbl 1148.65040
The authors design a variable neighborhood search metaheuristic to solve max-bisection problems. The max-bisection problem is transferred into an equivalent quadratic optimization problem which has the same feasible region as the max-cut problem. Then the modified variable neighborhood search metaheuristic by using a distinct local search is applied to solve the optimization problem. Some numerical experimental results are presented by comparing the proposed method to an existing approximate algorithm.

65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
Full Text: DOI
[1] D. Abraham, S. Ángel, F. Felipe, C. Raúl, A low-level hybridization between memetic algorithm and VNS for the max-cut problem, GECCO’05, June 25-29, 2005, Washington, DC, USA, pp. 999-1006.
[2] F. Alizadeh, J. Haeberly, M. Nayakkankuppam, M. Overton, S. Schmieta, SDPPACK user’s guide: Version 0.9 beta for MATLAB5.0, 1997.
[3] S.M. Antonio, D. Abraham, J.P. Juan, C. Raúl, High-performance VNS for the max-cut problem using commodity graphics hardware, 2005, Manuscript.
[4] Festa, P.; Pardalos, P.M.; Resende, M.G.C.; Ribeiro, C.C., Randomized heuristics for the MAX-CUT problem, Optim. methods software, 7, 1033-1058, (2002) · Zbl 1032.90073
[5] Frieze, A.; Jerrum, M., Improved approximation algorithm for MAX k-cut and MAX-bisection, Algorithmica, 18, 67-81, (1997) · Zbl 0873.68078
[6] Goemans, M.X.; Williamson, D.P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. assoc. comput. Mach., 42, 6, 1115-1145, (1995) · Zbl 0885.68088
[7] Halperin, E.; Zwick, U., A unified framework for obtaining improved approximation algorithms for maximum graph bisection problem, Random struct. algorithms, 20, 382-402, (2002) · Zbl 1017.68089
[8] Hansen, P.; Mladenovíc, N., Developments of variable neighborhood search, (), 415-439 · Zbl 1017.90130
[9] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[10] Mladenovíc, N.; Hansen, P., Variable neighborhood search, Comput. oper. res., 24, 1097-1100, (1997) · Zbl 0889.90119
[11] Xu, F.-m.; Xu, C.-x.; Xue, H.-g., A feasible direction algorithm without line search for solving MAX-bisection problem, J. comput. math., 23, 619-634, (2005) · Zbl 1086.65062
[12] Ye, Y., A 0.699-approximation algorithm for MAX-bisection, Math. programming, 90, 101-111, (2001) · Zbl 1059.90119
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.