Department of Mathematics University of Haifa COLLOQUIUM SPEAKER: Dr. Danny Hermelin (Max Planck Institut) TOPIC: Minimum Vertex Cover in Rectangle Graphs DATE: Tuesday, January 4th, 2011. (This corrects the date in a previous announcement which some of you may have seen.) TIME: 4:10 PM. PLACE Room 614 on the 6th floor of the Science & Education Building (opposite the main building), University of Haifa. Abstract In this talk I will consider the Minimum Vertex Cover problem in intersection graphs of axis-parallel rectangles on the plane. After discussing some motivations for this problem, I will present two approximation algorithms: The first is an EPTAS for non-crossing rectangle families, rectangle families R where R1 \ R2 is connected for every pair of rectangles R1 and R2 in R. The second algorithm achieves a factor of (1.5 + e) in general rectangle families for any fixed e > 0, and works also for the weighted variant of the problem. ------------------------------------------------------------------------ Technion Math Net-2 (TECHMATH2) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: <berger@math.haifa.ac.il>