A double-stage heuristic algorithm for the antibandwidth maximization problem via the linear bottleneck assignment optimization

doi:10.1016/j.cor.2026.107632

A double-stage heuristic algorithm for the antibandwidth maximization problem via the linear bottleneck assignment optimization

2026-08-01

0

PRE

AI

Eduardo Rodríguez-Tello

Z

Zequn Wei *

DOI：10.1016/j.cor.2026.107632

原文链接

原文求助

摘要

En 中文

antibandwidth 最大化问题是一个经典图布局问题，源自多处理器调度、射频分配和厌恶设施选址等应用。它涉及为图的顶点分配不同的整数标签，以使相邻顶点标签间的最小绝对差最大化。为解决该 NP-hard 问题，我们提出了一种双阶段启发式算法，集成了具有专用缩减邻域的局部优化阶段，以及包含贪婪分配步骤和优化分配步骤的贪婪优化扰动阶段。关键地，我们证明优化分配步骤可转化为求解线性瓶颈分配问题，该问题可通过阈值算法在多项式时间内求解。在 256 个基准实例上的实验结果表明，我们的算法通过实现 42 个改进的下界，在大多数其余实例上达到了最佳已知结果，从而优于当前最先进的方法。附加分析证实了算法关键组件对其整体性能的突出贡献。

Keyword:

Combinatorial optimization

Heuristic

Antibandwidth maximization problem

Linear bottleneck assignment problem

A double-stage heuristic algorithm for the antibandwidth maximization problem via the linear bottleneck assignment optimization

摘要

期刊

机构

引用论文