Geometric multicut

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Standard

Geometric multicut. / Abrahamsen, Mikkel; Giannopoulos, Panos; Löffler, Maarten; Rote, Günter.

46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. red. / Christel Baier; Ioannis Chatzigiannakis; Paola Flocchini; Stefano Leonardi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. 9 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 132).

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Harvard

Abrahamsen, M, Giannopoulos, P, Löffler, M & Rote, G 2019, Geometric multicut. i C Baier, I Chatzigiannakis, P Flocchini & S Leonardi (red), 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019., 9, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, bind 132, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Grækenland, 09/07/2019. https://doi.org/10.4230/LIPIcs.ICALP.2019.9

APA

Abrahamsen, M., Giannopoulos, P., Löffler, M., & Rote, G. (2019). Geometric multicut. I C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (red.), 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 [9] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Bind 132 https://doi.org/10.4230/LIPIcs.ICALP.2019.9

Vancouver

Abrahamsen M, Giannopoulos P, Löffler M, Rote G. Geometric multicut. I Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, red., 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. 9. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 132). https://doi.org/10.4230/LIPIcs.ICALP.2019.9

Author

Abrahamsen, Mikkel ; Giannopoulos, Panos ; Löffler, Maarten ; Rote, Günter. / Geometric multicut. 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. red. / Christel Baier ; Ioannis Chatzigiannakis ; Paola Flocchini ; Stefano Leonardi. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 132).

Bibtex

@inproceedings{be1488e1bca14164853e48276b947204,
title = "Geometric multicut",
abstract = "We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest “fence” F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC k-CUT, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n4 log3 n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2 − 4/3k)-approximation algorithm.",
keywords = "Clustering, Multicut, Steiner tree",
author = "Mikkel Abrahamsen and Panos Giannopoulos and Maarten L{\"o}ffler and G{\"u}nter Rote",
year = "2019",
doi = "10.4230/LIPIcs.ICALP.2019.9",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi",
booktitle = "46th International Colloquium on Automata, Languages, and Programming, ICALP 2019",
note = "46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 ; Conference date: 09-07-2019 Through 12-07-2019",

}

RIS

TY - GEN

T1 - Geometric multicut

AU - Abrahamsen, Mikkel

AU - Giannopoulos, Panos

AU - Löffler, Maarten

AU - Rote, Günter

PY - 2019

Y1 - 2019

N2 - We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest “fence” F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC k-CUT, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n4 log3 n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2 − 4/3k)-approximation algorithm.

AB - We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest “fence” F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC k-CUT, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n4 log3 n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2 − 4/3k)-approximation algorithm.

KW - Clustering

KW - Multicut

KW - Steiner tree

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

U2 - 10.4230/LIPIcs.ICALP.2019.9

DO - 10.4230/LIPIcs.ICALP.2019.9

M3 - Article in proceedings

AN - SCOPUS:85069197288

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019

A2 - Baier, Christel

A2 - Chatzigiannakis, Ioannis

A2 - Flocchini, Paola

A2 - Leonardi, Stefano

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019

Y2 - 9 July 2019 through 12 July 2019

ER -

ID: 231752405