Iterated multilevel simulated annealing for large-scale graph conductance minimization

DOI10.1016/J.INS.2021.04.102MaRDI QIDQ6071282zbMATH OpenFDO

Authors Zhi Lu, Jin-Kao Hao, Una Benlic, David Lesaint

Publication date 23 November 2023

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.INS.2021.04.102

zbMATH Keywords

combinatorial optimizationgraph theoryheuristicslarge-scale optimizationmetaheuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem
• Algorithms for graph partitioning problems by means of eigenspace relaxations
• An efficient approach for large scale graph partitioning
• Flow-based algorithms for local graph clustering
• \(D^{3}G^{2}A\): the dynamic distributed double guided genetic algorithm for the \(K\)-graph partitioning problem

Cites work

• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• A polynomial time algorithm for Rayleigh ratio on discrete variables: replacing spectral techniques for expander ratio, normalized cut, and Cheeger constant
• A survey on optimization metaheuristics
• An algorithm for improving graph partitions
• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Compact structure for sparse undirected graphs based on a clique graph partition
• Expander flows, geometric embeddings and graph partitioning
• Graph Partitioning and Graph Clustering
• Handbook of metaheuristics
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1561761 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• Integer Programming and Combinatorial Optimization
• Local network community detection with continuous optimization of conductance and weighted kernel k-means
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Multilevel refinement for combinatorial optimisation problems
• Optimization by simulated annealing
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• SOFSEM 2006: Theory and Practice of Computer Science
• Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem
• TTT plots: a perl program to create time-to-target plots

Cited in

(3)

• A hybrid ant colony algorithm for the winner determination problem
• Graph minors from simulated annealing for annealing machines with sparse connectivity
• Multilevel iterated tabu search for the multi-constraint graph partitioning problem

This page was built for publication: Iterated multilevel simulated annealing for large-scale graph conductance minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6071282)