Grid Bandwidth Minimization Problem: Simulated Annealing Approach
DOI:
https://doi.org/10.12723/mjs.sp1.9Keywords:
Grid embedding, Bandwidth, Simulated AnnealingAbstract
The Grid Bandwidth Minimization Problem (GBMP) is to find an embedding of a given graph into a host graph such that the bandwidth over all edges is minimised. It is an NP-complete problem with applications in VLSI circuit design, numerical analysis, computational biology, graph theory and scheduling. In this paper, a Simulated Annealing (SA) algorithm is developed for GBMP in which initial solution is generated using two problem-specific construction heuristics. Four neighborhood strategies are designed to explore the search space. Experiments conducted on benchmark instances achieve results which fall within the bounds whereas for grid graphs it attains optimal values.
References
Chung, Fan RK. "Labelings of graphs." Selected topics in graph theory 3, no. 25 (1988): 151-168.
Dıaz, Josep, Jordi Petit, and Marıa Serna. "A Survey on Graph Layout Problems." (2000).
Caprara, A., & Salazar-González, J. J. (2005). Laying out sparse graphs with provably minimum bandwidth. INFORMS Journal on Computing, 17(3), 356-373.
Raspaud, A., Sýkora, O., & Vrto, I. (2000, June). Congestion and dilation, similarities and differences: A survey. In SIROCCO (pp. 269-280).
Blum, A., Konjevod, G., Ravi, R., & Vempala, S. (2000). Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. Theoretical Computer Science, 235(1), 25-42.
Gupta, A. (2001). Improved bandwidth approximation for trees and chordal graphs. Journal of Algorithms, 40(1), 24-36.
Torres-Jimenez, J., Izquierdo-Marquez, I., Garcia-Robledo, A., Gonzalez-Gomez, A., Bernal, J., & Kacker, R. N. (2015). A dual representation simulated annealing algorithm
for the bandwidth minimization problem on graphs. Information Sciences, 303, 33-49.
Mladenovic, N., Urosevic, D., Pérez-Brito, D., & García-González, C. G. (2010). Variable neighbourhood search for bandwidth reduction. European Journal of Operational Research, 200(1), 14-27.
Rodríguez-García, Miguel Ángel, Jesus Sanchez-Oro, Eduardo Rodriguez-Tello, Eric Monfroy, and Abraham Duarte. "Two-dimensional bandwidth minimization problem:Exact and heuristic approaches." Knowledge-Based Systems 214 (2021): 106651.
Miller, Zevi, and James B. Orlin. "NP-completeness for minimizing maximum
edge length in grid embeddings." Journal of algorithms 6, no. 1 (1985): 10-16.
Hong, Jia-Wei, Kurt Mehlhorn, and Arnold L. Rosenberg. "Cost trade-offs in graph embeddings, with applications." Journal of the ACM (JACM) 30, no. 4 (1983):709-728.
Bezrukov, Sergei L., Joe D. Chavez, Larry H. Harper, Markus Röttger, and U-P. Schroeder. "Embedding of hypercubes into grids." In International Symposium on Mathematical Foundations of Computer Science, pp. 693-701. Springer, Berlin,
Heidelberg, 1998.
Bhatt, S. N., & Leighton, F. T. (1984). A framework for solving VLSI graph
layout problems. Journal of Computer and System Sciences, 28(2), 300-343.
Lin, Y. "On density lower bounds of two-dimensional bandwidth." In Journal Of Mathematical Research And Exposition-Chinese Edition-, vol. 16, pp. 343-349. Mathematical Research and Exposition, 1996.
Lin, Lan, and Yixun Lin. "Square-root rule of two-dimensional bandwidth problem∗." RAIRO-Theoretical Informatics and Applications 45, no. 4 (2011): 399- 411. https://doi.org/10.1051/ita/2011120
J.-X. Hao, Two-dimensional Bandwidth of Mobius Ladders and Other Graphs, Henan Sci. 18 (1) (2000) 15–20.
Rodríguez-García, M. A., Duarte, A., & Sánchez-Oro, J. (2018, May). GRASP with Path Relinking for 2D-Bandwidth Minimization Problem. In Proceedings of the International Conference on Learning and Optimization Algorithms: Theory and
Applications (pp. 1-5).
Aroca, J. A., & Anta, A. F. (2014, June). JAM: A Tabu-Based Two-Stage Simulated Annealing Algorithm for the Multidimensional Arrangement Problem. In International Workshop on Hybrid Metaheuristics (pp. 155-168). Springer, Cham.
Kirkpatrick, Scott. "Optimization by simulated annealing: Quantitative studies." Journal of statistical physics 34, no. 5 (1984): 975-986.
Additional Files
Published
Issue
Section
License
Copyright (c) 2023 Aditi Khandelwal, Kamal Srivastava, Gur Saran
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
