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>