[Colloquium] Chalermsook/MS Presentation/May 14, 2008

[Margaret Jaffey]

Just a reminder about Parinya Chalermsook's MS Presentation on  
Wednesday.

---------------------------------------------------------------------------------
Date:  Wednesday, May 14, 2008

Time:  2:30 p.m.

Place:  Ryerson 277

M.S. Candidate:  Parinya Chalermsook

M.S. Paper Title:  Maximum Independent Set of Rectangles

Abstract:
Maximum Independent Set is one of the most well-studied, fundamental  
combinatorial optimization problem. This problem and its special cases  
arise in many areas of computer science and often need to be solved as  
sub-routines of algorithms.

In this paper, we examine the Maximum Independent Set problem in the  
intersection graphs of axis-parallel rectangles in the plane and  
present an $O(\log \log n)$-approximation algorithm for the problem.  
Our algorithm is the first to give the guarantee of $o(\log n)$.  
Moreover, combining our algorithm with a straightforward divide-and- 
conquer algorithm given by Agarwal et al yields an improved  
approximation algorithm to the maximum independent set problem in $d$- 
box graphs which can be seen as generalization of the maximum  
independent set problem of rectangles to higher dimensions.  
Specifically, for any $d \ge 3$, we obtain an $O((\log n)^{d-2} \log  
\log n)$-approximation algorithm for the maximum independent set  
problem in the intersection graphs of boxes in $R^d$.

Advisors:  Prof. Julia Chuzhoy and Prof. Janos Simon

A draft copy of Parinya Chalermsook's MS paper is available in Ry 156.


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey                             margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)        (773) 702-6011
The University of Chicago                  http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=