Back to Search Start Over

A local search approximation algorithm for the multiway cut problem.

Authors :
Bloch-Hansen, Andrew
Samei, Nasim
Solis-Oba, Roberto
Source :
Discrete Applied Mathematics. Oct2023, Vol. 338, p8-21. 14p.
Publication Year :
2023

Abstract

In the multiway cut problem we are given a weighted undirected graph G = (V , E) and a set T ⊆ V of k terminals. The goal is to find a minimum weight set of edges E ′ ⊆ E with the property that by removing E ′ from G all the terminals become disconnected. In this paper we present a simple local search approximation algorithm for the multiway cut problem with approximation ratio 2 − 2 k . We present an experimental evaluation of the performance of our local search algorithm and show that it greatly outperforms the isolation heuristic of Dalhaus et al. and it has similar performance as the much more complex algorithms of Calinescu et al., Sharma and Vondrak, and Buchbinder et al. which have the currently best known approximation ratios for this problem. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
0166218X
Volume :
338
Database :
Academic Search Index
Journal :
Discrete Applied Mathematics
Publication Type :
Academic Journal
Accession number :
169704204
Full Text :
https://doi.org/10.1016/j.dam.2023.05.022