Advanced Scatter Search for the Max-Cut Problem

References

• Burer S., Monteiro R. D. C., Zang Y. Rank-two relaxation heuristics for max-cut and other binary quadratic programs. SIAM J. Optim. (2001) 12:503–521Crossref, Google Scholar
• Chang K. C., Du D.-Z. Eficient algorithms for layer assignment problems. IEEE Trans. Comput.-Aided Design (1987) 6:67–78Crossref, Google Scholar
• Chen R., Kajitani Y., Chan S. A graph-theoretic via minimization algorithm for two layer printed circuit boards. IEEE Trans. Circuits Systems (1983) 30:284–299Crossref, Google Scholar
• Duarte A., Martí R. Tabu search and GRASP for the maximum diversity problem. Eur. J. Oper. Res. (2007) 178:71–84Crossref, Google Scholar
• Festa P., Resende M. G. C., Resende M. G. C., Hansen P. GRASP: An annotated bibliography. Essays and Surveys in Metaheuristics (2001) (Kluwer Academic Publishers, Boston) 325–367Google Scholar
• Festa P., Pardalos P. M., Resende M. G. C., Ribeiro C. C. Randomized heuristics for the max-cut problem. Optim. Methods Software (2002) 7:1033–1058Crossref, Google Scholar
• Glover F. Ejection chains, reference structures and alternating methods for traveling salesman problems. Discrete Appl. Math. (1996) 65:223–253Crossref, Google Scholar
• Glover F., Laguna M.Tabu Search (1997) (Kluwer Academic Publishers, Boston) Crossref, Google Scholar
• Goemans M. X., Williamson D. P. Improved approximation algorithms for the max-cut and satisfability problems using semidefinite programming. J. ACM (1995) 42:1115–1145Crossref, Google Scholar
• Haglin D. J., Venkatesen S. M. Approximation and intractability results for the maximum cut problem and its variants. IEEE Trans. Comput. (1991) 40:110–113Crossref, Google Scholar
• Helmberg C., Rendl F. A spectral bundle method for semidefinite programming. SIAM J. Optim. (2000) 10:673–696Crossref, Google Scholar
• Homer S., Peinado M. Design and performance of parallel and distributed approximation algorithms for max cut. J. Parallel Distributed Comput. (1997) 46:48–61Crossref, Google Scholar
• Karp R. M., Miller R., Tatchers J. Reducibility among combinatorial problems. Complexity of Computer Computations (1972) (Plenum Press, New York) 85–103Crossref, Google Scholar
• Krishnan K., Mitchell J. E. A semidefinite programming based polyhedral cut and price approach for the maxcut problem. Comput. Optim. Appl. (2006) 33(1):51–71Crossref, Google Scholar
• Laguna M., Martí R. GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J. Comput. (1999) 11:44–52Link, Google Scholar
• Laguna M., Martí R.Scatter Search: Methodology and Implementations in C (2003) (Kluwer Academic Publishers, Boston) Crossref, Google Scholar
• Lin S., Kernighan B. An effective heuristic algorithm for the traveling salesman problem. Oper. Res. (1973) 21:498–516Link, Google Scholar
• Lovász L. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory (1979) 25:1–7Crossref, Google Scholar
• Poljak S., Tuza Z. A polynomial algorithm for constructing a large bipartite subgraph, with an application to a satisfiability problem. Canadian J. Math. (1982) 34:519–524Crossref, Google Scholar
• Sahni S., Gonzales T. P-complete approximation problem. J. ACM (1976) 46:48–61Google Scholar