Shared-Memory Branch-and-Reduce for Multiterminal Cuts

Monika Henzinger; Alexander Noe; Christian Schulz

doi:10.1137/1.9781611976007.4

Shared-Memory Branch-and-Reduce for Multiterminal Cuts

Monika Henzinger, Alexander Noe, Christian Schulz

Research Group Theory and Applications of Algorithms

Publications: Contribution to book › Contribution to proceedings › Peer Reviewed

Abstract

We introduce the fastest known exact algorithm for the multiterminal cut problem with k terminals. In particular, we engineer existing as well as new data reduction rules. We use the rules within a branch-and-reduce framework and to boost the performance of an ILP formulation. Our algorithms achieve improvements in running time of up to multiple orders of magnitudes over the ILP formulation without data reductions, which has been the de facto standard used by practitioners. This allows us to solve instances to optimality that are significantly larger than was previously possible.

Original language	English
Title of host publication	2020 Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020
Editors	Guy Blelloch, Irene Finocchi
Pages	42-55
Number of pages	14
ISBN (Electronic)	9781611976007
DOIs	https://doi.org/10.1137/1.9781611976007.4
Publication status	Published - 5 Jan 2020
Event	ALENEX 2020 - Salt Lake City, Utah, United States Duration: 5 Jan 2020 → 7 Jan 2020 https://www.siam.org/conferences/cm/conference/soda20

Conference

Conference	ALENEX 2020
Country/Territory	United States
City	Salt Lake City, Utah
Period	5/01/20 → 7/01/20
Internet address	https://www.siam.org/conferences/cm/conference/soda20

Austrian Fields of Science 2012

102031 Theoretical computer science

Access to Document

10.1137/1.9781611976007.4

http://eprints.cs.univie.ac.at/6201/

Cite this

@inproceedings{09909a6f237e4cd1b75ddac3c99e5f62,

title = "Shared-Memory Branch-and-Reduce for Multiterminal Cuts",

abstract = "We introduce the fastest known exact algorithm for the multiterminal cut problem with k terminals. In particular, we engineer existing as well as new data reduction rules. We use the rules within a branch-and-reduce framework and to boost the performance of an ILP formulation. Our algorithms achieve improvements in running time of up to multiple orders of magnitudes over the ILP formulation without data reductions, which has been the de facto standard used by practitioners. This allows us to solve instances to optimality that are significantly larger than was previously possible.",

author = "Monika Henzinger and Alexander Noe and Christian Schulz",

note = "Publisher Copyright: Copyright {\textcopyright} 2020 by SIAM; ALENEX 2020 ; Conference date: 05-01-2020 Through 07-01-2020",

year = "2020",

month = jan,

day = "5",

doi = "10.1137/1.9781611976007.4",

language = "English",

pages = "42--55",

editor = "Guy Blelloch and Irene Finocchi",

booktitle = "2020 Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020",

url = "https://www.siam.org/conferences/cm/conference/soda20",

}

TY - GEN

T1 - Shared-Memory Branch-and-Reduce for Multiterminal Cuts

AU - Henzinger, Monika

AU - Noe, Alexander

AU - Schulz, Christian

PY - 2020/1/5

Y1 - 2020/1/5

N2 - We introduce the fastest known exact algorithm for the multiterminal cut problem with k terminals. In particular, we engineer existing as well as new data reduction rules. We use the rules within a branch-and-reduce framework and to boost the performance of an ILP formulation. Our algorithms achieve improvements in running time of up to multiple orders of magnitudes over the ILP formulation without data reductions, which has been the de facto standard used by practitioners. This allows us to solve instances to optimality that are significantly larger than was previously possible.

AB - We introduce the fastest known exact algorithm for the multiterminal cut problem with k terminals. In particular, we engineer existing as well as new data reduction rules. We use the rules within a branch-and-reduce framework and to boost the performance of an ILP formulation. Our algorithms achieve improvements in running time of up to multiple orders of magnitudes over the ILP formulation without data reductions, which has been the de facto standard used by practitioners. This allows us to solve instances to optimality that are significantly larger than was previously possible.

UR - http://www.scopus.com/inward/record.url?scp=85079424307&partnerID=8YFLogxK

U2 - 10.1137/1.9781611976007.4

DO - 10.1137/1.9781611976007.4

M3 - Contribution to proceedings

SP - 42

EP - 55

BT - 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020

A2 - Blelloch, Guy

A2 - Finocchi, Irene

T2 - ALENEX 2020

Y2 - 5 January 2020 through 7 January 2020

ER -

Shared-Memory Branch-and-Reduce for Multiterminal Cuts

Abstract

Conference

Austrian Fields of Science 2012

Access to Document

Other files and links

Fingerprint

Cite this