BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Linda Kleist (TU Braunschweig)
DTSTART:20210617T141500Z
DTEND:20210617T160000Z
DTSTAMP:20260422T065353Z
UID:CJCS/21
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/CJCS/21/">On
  a Problem from Outer Space: Minimum Scan Covers</a>\nby Linda Kleist (TU 
 Braunschweig) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nA
 bstract\nIn this talk\, we investigate a natural geometric optimization pr
 oblem motivated by questions in the context of satellite communication and
  astrophysics. Given a graph embedded in Euclidean space\,  the *Minimum S
 can Cover Problem* (MSC) asks for a schedule of minimum makespan that *sca
 ns* all edges. In order to scan an edge\, the incident vertices rotate at 
 their positions such that they face each other. Thereby\, rotations take t
 ime proportional to the angular change.  \n \nOur work reveals close conne
 ctions to both the graph coloring problem and the minimum cut cover proble
 m. In particular\, we show that the minimum scan time for instances in 1D 
 and 2D lies in Θ(log χ(G))\, while it is not upper bounded by χ(G) in 3
 D. Unless P = NP\, these insights imply that no constant-factor approximat
 ion exists even in 1D. Going to higher dimensions\, we discuss hardness an
 d approximation results for special graph classes. The talk is based on jo
 int work with Sándor Fekete and Dominik Krupke.\n
LOCATION:https://researchseminars.org/talk/CJCS/21/
END:VEVENT
END:VCALENDAR