A unified Parallel Evolutionary Algorithm Framework (PEAF) is proposed, which combines structure-inheriting crossover operators, a hierarchical mutation mechanism based on the Multiple Mutation Heuristic and the Auxiliary Cut Mutation Heuristic, and a diversity-preserving selection strategy.
Abstract
Graph k-CUT problems include many important variants whose objectives combine cut value, volume, and cardinality terms in different ways. Most existing algorithms are designed for individual formulations, which limits their transferability across related models. In this paper, we organize a broad family of graph partitioning problems into two classes, MaxGCP and MinGCP, according to their optimization orientation and balance-related structure. Based on this classification, we propose a unified Parallel Evolutionary Algorithm Framework (PEAF). This framework combines structure-inheriting crossover operators, a hierarchical mutation mechanism based on the Multiple Mutation Heuristic (MMH) and the Auxiliary Cut Mutation Heuristic (ACMH), and a diversity-preserving selection strategy. Extensive experiments on G-set with k \in\{2, 3, 4, 5\} show that PEAF-ACMH consistently outperforms Gurobi on nine representative k-CUT problems. For MaxGCP, PEAF-ACMH improves several best-known solutions for Max-k-Cut with k \geq 3, and through numerical bounds derived from its relation to Max-k-Cut, verifies the high quality of the obtained solutions for Judicious-k-Partition and AntiCheeger-k-Cut. The results further indicate that Judicious-k-Partition usually yields more balanced partitions than AntiCheeger-k-Cut. For MinGCP, theoretical and computational comparisons show that Cheeger-k-Cut and Sparsest-k-Cut produce more balanced partitions than Normalized-k-Cut and Ratio-k-Cut, respectively. PEAF-ACMH also obtains highly similar partitions for Min-k-Cut and MinMax-k-Cut within short running times, providing numerical evidence for their structural affinity. These results demonstrate that PEAF is both an effective unified solver and a useful tool for revealing structural properties of graph k-CUT models.
CP-McSplitDAL is introduced, a cooperative parallel framework that extends McSplit-DAL with portfolio-style multi-heuristic search on shared-memory machines and achieves lower regret in time to optimality, improves solution quality under time limits, and better exploits multi-core hardware than non-cooperative or purely sequential variants.
Lorenzo Cardone, Stefano Quer· International Conference on...· 0 citations
This paper addresses the minimum linear arrangement problem, a classical graph layout problem in which the objective is to minimize the sum of absolute differences between the labels assigned to adjacent vertices in undirected graphs. The paper introduces small boundary (SB(k)), a family of linear-time greedy heuristics that guide vertex labeling through a prioritization scheme based on the structure of labeled and k levels of unlabeled vertex neighborhoods. An extensive experimental evaluation on 26 large-scale real-world graphs demonstrates that the proposed heuristic with k=2 consistently outperforms 19 established low-cost graph-theoretic reordering algorithms, including the leading constructive method used within a high-performing metaheuristic algorithm for the problem. Additionally, the SB(2) heuristic outperforms this high-performing metaheuristic algorithm while requiring up to 800 times less computational effort. The paper further shows that integrating SB(2) as the initialization procedure within this metaheuristic yields improved solution quality, highlighting its effectiveness as both a standalone heuristic and a high-quality initializer. Overall, the proposed approach provides a fast, scalable, and practical solution for tackling MinLA on large-scale graphs.
S. D. de Oliveira, A. A. D. de Abreu· Journal of Heuristics· 0 citations
Coloring the vertices, edges or faces of a graph so that no two adjacent elements share a label is among the oldest problems in graph theory, and one of the few whose reach extends into exam timetables and wireless spectrum allocation as it does into pure combinatorics. This survey draws together the problem’s theoretical core – vertex, edge, face, list and total coloring – with the algorithms built to solve it and the industries that now depend on those algorithms. Because coloring is NP-hard, we trace the field’s progression from exact and greedy methods (Welsh-Powell, DSATUR, backtracking) through metaheuristics that trade optimality for scale (genetic algorithms, tabu search, simulated annealing, ant colony and artificial bee colony optimization), to the graph neural network and quantum-inspired solvers that have emerged in recent years. Rather than treating theory, algorithms and applications as separate literatures, we connect them directly: each application – examination and crew scheduling, frequency assignment, compiler register allocation, cartographic map coloring – is traced back to the specific coloring variant and algorithm family the literature actually uses, while the algorithm families themselves are compared head-to-head on complexity, solution quality and scalability rather than catalogued one at a time. This comparative structure, together with its coverage of recent learning-based solvers, is what distinguishes this survey from the standard references on the subject. We close by outlining where the field’s open problems remain, from long standing conjectures to the still-unanswered question of whether learned heuristics can match classical methods at real-world scale.
Jisha Ann Abraham, C. Wilfred, Thomaskutty Stephen· International journal of com...· 0 citations
What problems can one solve on a tournament if only its score sequence is known? Tournaments are oriented complete graphs that form an extensively-studied class of directed graphs (digraphs), both from combinatorial and algorithmic perspectives. Over the years, researchers have identified multiple classical digraph problems that can be solved on a tournament from only its score sequence (indegree sequence). These problems include acyclicity testing and topological sorting [Chakrabarti, Ghosh, McGregor, and Vorotnikova; SODA'20], $s,t$-reachability, strong connectivity, and decomposition into strongly connected components (SCC) [Ghosh and Kuchlous; ESA'24], and vertex-ordering problems such as cutwidth and optimal linear arrangement [Barbero, Paul, and Pilipczuk; ICALP'17]. These prior works showed the sufficiency of the score sequence by designing distinct algorithms for the individual problems. In this work, we give a simple unified framework that solves all these problems using only indegrees and, in fact, completely characterises the class of problems that is determined by the indegree information: problems whose answers are invariant under cycle reversals. This characterisation is a special case of a much more general result that we establish: for any arbitrary digraph, the knowledge of its skeleton (underlying undirected graph) and the vertex indegrees completely determines its properties that are invariant under cycle reversal. As a byproduct of our results, we obtain algorithms for a variety of connectivity-based, cut-based, and vertex-ordering problems on tournaments and ``almost tournaments''in the streaming, the two-player communication, and the cut-query models of computation. Some of these algorithms match existing optimal bounds and others provide bounds improving the state of the art.
Prantar Ghosh, Sahil Kuchlous, Shravan Mehra et al.· Embedded Systems and Applica...· 0 citations
Multi-objective combinatorial optimization arises in a wide range of problems and applications, including the canonical multi-objective MaxCut problem. Differentiable single-instance quadratic methods have recently achieved remarkable performance in single-objective combinatorial optimization. In this paper, we develop a differentiable framework for multi-objective MaxCut by combining an adjacency-based quadratic formulation with linear scalarization, thereby reducing the problem to a preference-conditioned single-objective signed-weight MaxCut problem. Theoretically, we characterize the stationary points of the resulting signed-weight formulation and show how they induce preference-conditioned fixed points on the Pareto front. Computationally, unlike conventional heuristics and branch-and-bound methods, our approach is GPU-parallelizable and can therefore benefit from substantial performance speedups. We term our algorithm Multi-objective QUadratic Combinatorial Optimization (MO-QUCO) and its parallelized variant pMO-QUCO. Empirically, across different multi-layered (and weight distributions) graphs, we show that both our CPU-only and GPU-based algorithms outperform SOTA exact and heuristic methods in terms of wall-clock runtime and objective quality. Despite operating under different computational settings, MO-QUCO also outperforms the SOTA quantum method.
Jinghang Huang, Alvaro Velasquez, Jia Liu et al.· 0 citations
Graph colouring, a fundamental problem in combinatorial optimization, plays a critical role in various real-world applications such as register allocation, scheduling, and frequency assignment. Efficiently solving the graph colouring problem under multiple constraints remains a major computational challenge, particularly for large and complex graphs. This study addresses these limitations by proposing a hybrid optimization model that integrates Quantum-Inspired Evolutionary Algorithms (QIEA) with an Improved Particle Swarm Optimization (IPSO) technique. The proposed model leverages the probabilistic representation and parallel search capabilities of QIEA along with the adaptive learning and velocity adjustment features of IPSO to explore the solution space effectively. The primary objective is to minimize the number of colours used while satisfying adjacency, capacity, and dependency constraints. Experimental evaluations conducted on benchmark graph instances demonstrate that the hybrid model significantly outperforms existing evolutionary and heuristic methods in terms of convergence speed, constraint satisfaction, and colouring efficiency. These results affirm the potential of the QIEA-IPSO hybrid in solving complex multi-constrained graph colouring problems.
Unknown authors· Adolescência e Saúde· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
