BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We study the following separation problem: Given a collection 
 of colored objects in the plane\, compute a shortest "fence" F\, i.e.\, a u
 nion of curves of minimum total length\, that separates every two objects o
 f 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. W
 e refer to the problem as GEOMETRIC k-CUT\, where k is the number of differ
 ent colors\, as it can be seen as a geometric analogue to the well-studied 
 multicut problem on graphs. We first give an O(n^4 log^3 n)-time algorithm 
 that computes an optimal fence for the case where the input consists of pol
 ygons of two colors and n corners in total. We then show that the problem i
 s NP-hard for the case of three colors. Finally\, we give a 4/3*1.2965-appr
 oximation algorithm.   Joint work with Panos Giannopoulos\, Maarten Löffler
 \, and Günter Rote. Presented at ICALP 2019. 
DTSTAMP:20200330T142000
DTSTART:20200427T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9 
 \n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Mikkel Abrahamsen (University of Copenhagen): Geometric Multicut: S
 hortest Fences for Separating Groups of Objects in the Plane - cancelled
UID:105463982@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20200427-L-Abrahamsen.html
END:VEVENT
END:VCALENDAR