A multiple search operator heuristic for the max-k-cut problem

DOI10.1007/S10479-016-2234-0zbMATH Open1357.90122arXiv1510.09156OpenAlexW2242324393MaRDI QIDQ513573FDOQ513573

Authors: Fuda Ma, Jin-Kao Hao 

Publication date: 7 March 2017

Published in: Annals of Operations Research (Search for Journal in Brave)

Abstract: The max-k-cut problem is to partition the vertices of a weighted graph $G=(V,E)$ into $kgeq2$ 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 $k=2$. 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 $k=2$ (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.

Full work available at URL: https://arxiv.org/abs/1510.09156

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

zbMATH Keywords

graph partitionheuristicsmultiple search strategiesmax-k-cut and max-cuttabu list

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
• Title not available (Why is that?)
• Introduction to algorithms
• Title not available (Why is that?)
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Probabilistic GRASP-tabu search algorithms for the UBQP problem
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• A projected gradient algorithm for solving the maxcut SDP relaxation
• Title not available (Why is that?)
• Title not available (Why is that?)
• A discrete dynamic convexized method for the max-cut problem
• A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
• Advanced scatter search for the max-cut problem
• Memetic search for the max-bisection problem
• Randomized heuristics for the Max-Cut problem
• Realignment in the National Football League: Did they do it right?
• Title not available (Why is that?)
• A graph-theoretic via minimization algorithm for two-layer printed circuit boards
• Title not available (Why is that?)
• Speeding up a memetic algorithm for the max-bisection problem
• Fast approximation algorithms on maxcut, k-coloring, and k-color ordering for VLSI applications
• An Efficient Memetic Algorithm for theMax-Bisection Problem
• Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel

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

Uses Software

• CirCut
• Tabu search

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)