--- _id: '9227' abstract: - lang: eng text: 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. alternative_title: - LNCS article_processing_charge: No author: - first_name: Andrew full_name: Bloch-Hansen, Andrew last_name: Bloch-Hansen - first_name: Nasim full_name: Samei, Nasim id: C1531CAE-36E9-11EA-845F-33AA3DDC885E last_name: Samei - first_name: Roberto full_name: Solis-Oba, Roberto last_name: Solis-Oba citation: ama: '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. Springer Nature; 2021:346-358. doi:10.1007/978-3-030-67899-9_28' apa: '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' chicago: 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. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-67899-9_28. ieee: 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. ista: '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 Mathematics, LNCS, vol. 12601, 346–358.' mla: 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. short: A. Bloch-Hansen, N. Samei, R. Solis-Oba, in:, Conference on Algorithms and Discrete Applied Mathematics, Springer Nature, 2021, pp. 346–358. conference: end_date: 2021-02-13 location: Rupnagar, India name: 'CALDAM: Conference on Algorithms and Discrete Applied Mathematics' start_date: 2021-02-11 date_created: 2021-03-07T23:01:25Z date_published: 2021-01-28T00:00:00Z date_updated: 2023-10-10T09:29:08Z day: '28' department: - _id: VlKo doi: 10.1007/978-3-030-67899-9_28 intvolume: ' 12601' language: - iso: eng month: '01' oa_version: None page: 346-358 publication: Conference on Algorithms and Discrete Applied Mathematics publication_identifier: eissn: - 1611-3349 isbn: - '9783030678982' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Experimental evaluation of a local search approximation algorithm for the multiway cut problem type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 12601 year: '2021' ...