Algebra for transforming the structure of the search spaces associated with the combinatorial optimization problems
Abstract:
This article proposes the classification of the search spaces associated with the combinatorial optimization problems based on the type of their constituent solutions. The spaces belonging to each identified class are accompanied by the corresponding graph models. Against this background, the article introduces the original algebra allowing the representation of the search spaces in the unified homogeneous form. The proposed algebra consists of a set of transformations given in an analytical form and illustrated by the modifications of the graph models constructed for the search spaces.
References:
W. K. Mak and D. F. Wong, “A Fast Hypergraph Min-Cut Algorithm for Circuit Partitioning”, Integration, the VLSI Journal, Vol. 30(1), 2000, pp. 1 – 11.
View in Google ScholarY. Fan, Q. Liang, Y. Chen, X. Yan, C. Hu, H. Yao, C. Liu, and D. Zeng, “Executing Time and Cost-Aware Task Scheduling in Hybrid Cloud Using a Modified DE Algorithm”, Computational Intelligence and Intelligent Systems. Communications in Computer and Information Science, Vol. 575, 2016, pp. 74 – 83.
View in Google ScholarR. Cohen and G. Grebla, “Multidimensional OFDMA Scheduling in a Wireless Network With Relay Nodes”, IEEE/ACM Transactions on Networking, Vol. 23(6), 2015, pp. 1765 – 1776.
View in Google ScholarH. Kellerer, U. Pferschy, and D. Pisinger. “Knapsack Problems”, Springer, 2004
View in Google ScholarA. Potebnia, “Method for Classification of the Computational Problems on the Basis of the Multifractal Division of the Complexity Classes”, Proceedings of the Third International Scientific-Practical Conference on Problems of Infocommunications. Science and Technology (PIC S&T), 2016, pp. 1 – 4.
View in Google ScholarA. Potebnia, “Representation of the Greedy Algorithms Applicability for Solving the Combinatorial Optimization Problems Based on the Hypergraph Mathematical Structure”, Proceedings of the 14th International Conference on The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM), 2017, pp. 328 – 332.
View in Google ScholarR. Franz, “Design of Modern Heuristics: Principles and Application”, Springer-Verlag Berlin Heidelberg, 2011.
View in Google ScholarC. Reidys and P. Stadler, “Combinatorial Landscapes”, SIAM REVIEW, Vol. 44, 2002, pp. 3 – 54.
View in Google ScholarA. K. Kamrani and E. A. Nasr, “Engineering Design and Rapid Prototyping”, Springer US, 2010.
View in Google ScholarT. Van Luong, N. Melab, E.G. Talbi, “GPU Computing for Parallel Local Search Metaheuristic Algorithms”, IEEE Transactions on Computers, Vol. 62(1), 2013, pp. 173 – 185.
View in Google ScholarE. Aarts and J. K. Lenstra, “Local Search in Combinatorial Optimization”, John Wiley & Sons Ltd., 1997.
View in Google ScholarC. Blum and A. Roli, “Metaheuristics in Combinatorial Optimization: Overview and conceptual comparison”, ACM Computing Surveys, Vol. 35(3), 2003, pp. 268 – 308.
View in Google Scholar
