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

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

2010-09-24

arxiv.org/abs/1009.4880v1

Computer Science

Data Structures and Algorithms

Scientific paper

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^2) 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).

Affiliated with

Also associated with

No associations

Rating

An Efficient Implementation of the Robust Tabu Search Heuristic for Sparse Quadratic Assignment Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Efficient Implementation of the Robust Tabu Search Heuristic for Sparse Quadratic Assignment Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient Implementation of the Robust Tabu Search Heuristic for Sparse Quadratic Assignment Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-275283