Tabu search for graph partitioning |
| |
Authors: | Erik Rolland Hasan Pirkul Fred Glover |
| |
Institution: | (1) The A. Gary Anderson Graduate School of Management, University of California, 92521 Riverside, CA, USA;(2) Academic Faculty of Accounting & MIS, The Ohio State University, 43210 Columbus, OH, USA;(3) Graduate School of Business and Administration, University of Colorado at Boulder, 80309 Boulder, CO, USA |
| |
Abstract: | In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements. |
| |
Keywords: | Heuristic search graph partitioning tabu search |
本文献已被 SpringerLink 等数据库收录! |
|