A discrete filled function algorithm for approximate global solutions of max-cut problems

✍ Scribed by Ai-Fan Ling; Cheng-Xian Xu; Feng-Min Xu

• Publisher: Elsevier Science
• Year: 2008
• Tongue: English
• Weight: 245 KB
• Volume: 220
• Category: Article
• ISSN: 0377-0427
• DOI: 10.1016/j.cam.2007.09.012

✦ Synopsis

A discrete filled function algorithm is proposed for approximate global solutions of max-cut problems. A new discrete filled function is defined for max-cut problems and the properties of the filled function are studied. Unlike general filled function methods, using the characteristic of max-cut problems, the parameters in proposed filled function need not be adjusted. This greatly increases the efficiency of the filled function method. By combining a procedure that randomly generates initial points for minimization of the filled function, the proposed algorithm can greatly reduce the calculation cost and be applied to large scale max-cut problems. Numerical results on different sizes and densities test problems indicate that the proposed algorithm is efficient and stable to get approximate global solutions of max-cut problems.