---
_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: <i>Conference on Algorithms
    and Discrete Applied Mathematics</i>. Vol 12601. Springer Nature; 2021:346-358.
    doi:<a href="https://doi.org/10.1007/978-3-030-67899-9_28">10.1007/978-3-030-67899-9_28</a>'
  apa: 'Bloch-Hansen, A., Samei, N., &#38; Solis-Oba, R. (2021). Experimental evaluation
    of a local search approximation algorithm for the multiway cut problem. In <i>Conference
    on Algorithms and Discrete Applied Mathematics</i> (Vol. 12601, pp. 346–358).
    Rupnagar, India: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-67899-9_28">https://doi.org/10.1007/978-3-030-67899-9_28</a>'
  chicago: Bloch-Hansen, Andrew, Nasim Samei, and Roberto Solis-Oba. “Experimental
    Evaluation of a Local Search Approximation Algorithm for the Multiway Cut Problem.”
    In <i>Conference on Algorithms and Discrete Applied Mathematics</i>, 12601:346–58.
    Springer Nature, 2021. <a href="https://doi.org/10.1007/978-3-030-67899-9_28">https://doi.org/10.1007/978-3-030-67899-9_28</a>.
  ieee: A. Bloch-Hansen, N. Samei, and R. Solis-Oba, “Experimental evaluation of a
    local search approximation algorithm for the multiway cut problem,” in <i>Conference
    on Algorithms and Discrete Applied Mathematics</i>, 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.” <i>Conference on Algorithms and Discrete
    Applied Mathematics</i>, vol. 12601, Springer Nature, 2021, pp. 346–58, doi:<a
    href="https://doi.org/10.1007/978-3-030-67899-9_28">10.1007/978-3-030-67899-9_28</a>.
  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'
...