A multiple search operator heuristic for the max-k-cut problem
From MaRDI portal
Abstract: The max-k-cut problem is to partition the vertices of a weighted graph into disjoint subsets such that the weight sum of the edges crossing the different subsets is maximized. The problem is referred as the max-cut problem when . In this work, we present a multiple operator heuristic (MOH) for the general max-k-cut problem. MOH employs five distinct search operators organized into three search phases to effectively explore the search space. Experiments on two sets of 91 well-known benchmark instances show that the proposed algorithm is highly effective on the max-k-cut problem and improves the current best known results (new lower bounds) of most of the tested instances. For the popular special case (i.e., the max-cut problem), MOH also performs remarkably well by discovering 6 improved best known results. We provide additional studies to shed light on the alternative combinations of the employed search operators.
Recommendations
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- Randomized heuristics for the Max-Cut problem
- Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
- The capacitated max \(k\)-cut problem
- A discrete dynamic convexized method for the max-cut problem
Cites work
- scientific article; zbMATH DE number 3880601 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 1332666 (Why is no real title available?)
- scientific article; zbMATH DE number 1062113 (Why is no real title available?)
- scientific article; zbMATH DE number 2159019 (Why is no real title available?)
- scientific article; zbMATH DE number 2086928 (Why is no real title available?)
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- A discrete dynamic convexized method for the max-cut problem
- A graph-theoretic via minimization algorithm for two-layer printed circuit boards
- A projected gradient algorithm for solving the maxcut SDP relaxation
- Advanced scatter search for the max-cut problem
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- An Efficient Memetic Algorithm for theMax-Bisection Problem
- Fast approximation algorithms on maxcut, k-coloring, and k-color ordering for VLSI applications
- Introduction to algorithms
- Memetic search for the max-bisection problem
- Probabilistic GRASP-tabu search algorithms for the UBQP problem
- Randomized heuristics for the Max-Cut problem
- Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
- Realignment in the National Football League: Did they do it right?
- Speeding up a memetic algorithm for the max-bisection problem
- Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
Cited in
(9)- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- Experimental evaluation of a local search approximation algorithm for the multiway cut problem
- Advanced scatter search for the max-cut problem
- Efficient enumeration of the optimal solutions to the correlation clustering problem
- Meta-heuristics and artificial intelligence
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- A Heuristic Solution of a Cutting Problem Using Hypergraphs
- Fast r-flip move evaluations via closed-form formulae for Boolean quadratic programming problems with generalized upper bound constraints
This page was built for publication: A multiple search operator heuristic for the max-k-cut problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513573)
