A local search approximation algorithm for the multiway cut problem

DOI10.1016/J.DAM.2023.05.022MaRDI QIDQ6166037zbMATH OpenOpenAlexFDO

Authors Andrew Bloch-Hansen, Nasim Samei, Roberto Solis-Oba

Publication date 2 August 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2023.05.022

zbMATH Keywords

local searchapproximation algorithmsmultiway cutexperimental evaluation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• An improved approximation algorithm of MULTIWAY CUT.
• scientific article; zbMATH DE number 1775387
• Generalized \(k\)-multiway cut problems
• A simple algorithm for the multiway cut problem
• Algorithm Theory - SWAT 2004

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• scientific article; zbMATH DE number 1342124 (Why is no real title available?)
• scientific article; zbMATH DE number 1775387 (Why is no real title available?)
• Experimental evaluation of a local search approximation algorithm for the multiway cut problem
• Local Search Heuristics for k-Median and Facility Location Problems
• Multiprocessor Scheduling with the Aid of Network Flow Algorithms
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Recent directions in netlist partitioning: a survey
• Simplex partitioning via exponential clocks and the multiway cut problem
• Simplex transformations and the multiway cut problem
• The Complexity of Multiterminal Cuts

Cited in

(4)

• Experimental evaluation of a local search approximation algorithm for the multiway cut problem
• Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
• An improved approximation algorithm of MULTIWAY CUT.
• Smoothed Analysis of Local Search for the Maximum-Cut Problem

This page was built for publication: A local search approximation algorithm for the multiway cut problem

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