.png){kind=icon}
Return
A double-stage heuristic algorithm for the antibandwidth maximization problem via the linear bottleneck assignment optimization
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2026.107632.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The antibandwidth maximization problem is a classic graph layout problem arising in applications such as multiprocessor scheduling, radio frequency assignment, and obnoxious facility location. It involves assigning distinct integer labels to the vertices of a graph such that the minimum absolute difference between the labels of adjacent vertices is maximized. To solve this NP-hard problem, we propose a double-stage heuristic algorithm integrating a local optimization stage with a dedicated reduced neighborhood, and a greedy optimized perturbation stage including a greedy assignment step as well as an optimized assignment step. Crucially, we demonstrate that the optimized assignment step can be transformed into solving the linear bottleneck assignment problem, which is solvable in polynomial time via a threshold algorithm. Experimental results across 256 benchmark instances show that our algorithm outperforms state-of-the-art methods by achieving 42 improved lower bounds while matching the best-known results on the majority of the remaining instances. Additional analysis confirms the critical contribution of the algorithm's key components to its overall performance.
Keywords:
Combinatorial optimization
Heuristic
Antibandwidth maximization problem
Linear bottleneck assignment problem
Journal
C
IF:
4.3
Papers:
265
Citations:
0
Organization
View more organizations
Cited Papers
No cited papers available