[Colloquium] Chalermsook/MS Presentation/May 14, 2008
Margaret Jaffey
margaret at cs.uchicago.edu
Wed Apr 30 09:24:18 CDT 2008
This is an announcement of Parinya Chalermsook's MS Presentation.
---------------------------------------------------------------------------------
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 will be available soon
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
More information about the Colloquium
mailing list