๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the quality of local search for the quadratic assignment problem

โœ Scribed by Eric Angel; Vassilis Zissimopoulos

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
573 KB
Volume
82
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

โœฆ Synopsis

Local search is widely used to solve approximately NP-complete combinatorial optimization problems. But, little is known about quality of obtained local minima, for a given neighborhood. We concentrate on one of the most difficult optimization problems. the Quadratic Assignment Problem, and we give an upper bound for the quality of solutions obtained with deepest local search. Moreover, other recently established results on the traveling salesman problem, the graph bipartitioning problem and the maximum independent set problem can be deduced as particular cases.

๐Ÿ“œ SIMILAR VOLUMES

Robust taboo search for the quadratic as
Robust taboo search for the quadratic assignment problem
โœ E. Taillard ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 635 KB

Taillard, E., Robust taboo search for the quadratic assignment problem, Parallel Computing 17 (1991) 443-455. An adaptation of taboo search to the quadratic assignment problem is discussed in this paper This adaptation is efficient and robust, requiring less complexity and fewer parameters than ear

On the quadratic assignment problem
On the quadratic assignment problem
โœ A.M. Frieze; J. Yadegar ๐Ÿ“‚ Article ๐Ÿ“… 1983 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 537 KB