An Efficient Implementation of the Robust Tabu Search Heuristic for Sparse Quadratic Assignment Problems

2010/09/24 by Gerald Paul, Paul, Gerald
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1009.4880

arxiv created 2010/09/24 · arxiv updated 2010/09/27

Abstract

We propose and develop an efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems. The traditional implementation of the heuristic applicable to all quadratic assignment problems is of O(N²) complexity per iteration for problems of size N. Using multiple priority queues to determine the next best move instead of scanning all possible moves, and using adjacency lists to minimize the operations needed to determine the cost of moves, we reduce the asymptotic complexity per iteration to O(N log N ). For practical sized problems, the complexity is O(N).

Related

• A Variable Depth Sequential Search Heuristic for the Quadratic Assignment Problem
• Comparative Performance of Tabu Search and Simulated Annealing Heuristics for the Quadratic Assignment Problem
• O(1) Delta Component Computation Technique for the Quadratic Assignment Problem
• GPU-accelerated Parallel Solutions to the Quadratic Assignment Problem
• An efficient implementation of the simulated annealing heuristic for the quadratic assignment problem