Experimental evaluation of a local search approximation algorithm for the multiway cut problem

Bloch-Hansen A, Samei N, Solis-Oba R. 2021. Experimental evaluation of a local search approximation algorithm for the multiway cut problem. Conference on Algorithms and Discrete Applied Mathematics. CALDAM: Conference on Algorithms and Discrete Applied MathematicsLNCS vol. 12601, 346–358.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English

Scopus indexed
Author
Bloch-Hansen, Andrew; Samei, NasimIST Austria; Solis-Oba, Roberto
Department
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−2k . 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.
Publishing Year
Date Published
2021-01-28
Proceedings Title
Conference on Algorithms and Discrete Applied Mathematics
Volume
12601
Page
346-358
Conference
CALDAM: Conference on Algorithms and Discrete Applied Mathematics
Conference Location
Rupnagar, India
Conference Date
2021-02-11 – 2021-02-13
ISSN
eISSN
IST-REx-ID

Cite this

Bloch-Hansen A, Samei N, Solis-Oba R. Experimental evaluation of a local search approximation algorithm for the multiway cut problem. In: Conference on Algorithms and Discrete Applied Mathematics. Vol 12601. LNCS. Springer Nature; 2021:346-358. doi:10.1007/978-3-030-67899-9_28
Bloch-Hansen, A., Samei, N., & Solis-Oba, R. (2021). Experimental evaluation of a local search approximation algorithm for the multiway cut problem. In Conference on Algorithms and Discrete Applied Mathematics (Vol. 12601, pp. 346–358). Rupnagar, India: Springer Nature. https://doi.org/10.1007/978-3-030-67899-9_28
Bloch-Hansen, Andrew, Nasim Samei, and Roberto Solis-Oba. “Experimental Evaluation of a Local Search Approximation Algorithm for the Multiway Cut Problem.” In Conference on Algorithms and Discrete Applied Mathematics, 12601:346–58. LNCS. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-67899-9_28.
A. Bloch-Hansen, N. Samei, and R. Solis-Oba, “Experimental evaluation of a local search approximation algorithm for the multiway cut problem,” in Conference on Algorithms and Discrete Applied Mathematics, Rupnagar, India, 2021, vol. 12601, pp. 346–358.
Bloch-Hansen A, Samei N, Solis-Oba R. 2021. Experimental evaluation of a local search approximation algorithm for the multiway cut problem. Conference on Algorithms and Discrete Applied Mathematics. CALDAM: Conference on Algorithms and Discrete Applied MathematicsLNCS vol. 12601, 346–358.
Bloch-Hansen, Andrew, et al. “Experimental Evaluation of a Local Search Approximation Algorithm for the Multiway Cut Problem.” Conference on Algorithms and Discrete Applied Mathematics, vol. 12601, Springer Nature, 2021, pp. 346–58, doi:10.1007/978-3-030-67899-9_28.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search