GRASP with path relinking heuristics for the antibandwidth problem

A. Duarte, R. MartÃ, M. G. C. Resende, R. M. A. Silva

Networks, vol. 58, pp. 171-189, 2011, DOI: 10.1002/net.20418

**ABSTRACT**

problem. In the antibandwidth problem, one is given an undirected graph with N nodes and must label the nodes in a way that each node receives a

unique label from the set {1, 2, ..., N}, such that, among all adjacent node pairs, the minimum difference between the node labels is maximized.

Computational results show that only small instances of this problem can be solved exactly (to optimality) with a commercial integer programming

solver and that the heuristics find high-quality solutions in much less time than the commercial solver.

PDF file of full paper

Go back

Mauricio G.C. Resende's Home PageLast modified: