[Colloquium] Chalermsook/Dissertation Defense/May 3, 2012

[Margaret Jaffey]

Note: Parinya's defense on May 3rd will be held at the Toyota
Technological Institute, 6045 S. Kenwood Ave.

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Parinya Chalermsook

Date:  Thursday, May 3, 2012

Time:  1:00 PM

Place:  TTIC 501

Title: Approximation Algorithms for Integral Concurrent Flow,
Independent Set of Rectangles, and Fire Containment Problems

Abstract:
We study the approximability of three NP-hard combinatorial
optimization problems that arise in various areas of computer science:
Integral Concurrent Flow, Maximum Independent Set of Rectangles, and
Fire Containment problems.

In the first part, we study the integral counterpart of the classical
Maximum Concurrent Flow problem, as well as its variants. In the basic
version of this problem (basic-ICF), we are given an undirected graph
G with edge capacities c(e), a subset T of vertices called terminals,
and a demand D(t,t') for every pair (t,t') of the terminals. The goal
is to find the maximum value \lambda, and a collection S of paths,
such that every pair (t,t') of terminals is connected by \lambda
D(t,t') paths in S, and the number of paths containing any edge e is
at most c(e). We show a poly-logarithmic approximation algorithm that
violates the edge capacities by only a constant factor. The key
ingredient of our results is a new graph splitting technique which
could be of independent interest. The results in this part are based
on joint work with Julia Chuzhoy, Alina Ene, and Shi Li in STOC 2012.

In the second part of the thesis, we turn to a geometric problem.
Given a collection of rectangles, our goal is to select a
non-overlapping sub-collection of maximum cardinality. This problem
has many applications, as well as connections to other problems in
various areas of computer science. The problem was introduced in 1997
together with a simple O(log n) approximation algorithm for it.
Despite many attempts from different groups of researchers, the O(log
n) upper bound remained the best known. We show an O(log log n)
approximation algorithm. Our algorithm illustrates a connection
between this problem and a half-century old rectangle coloring
problem. The main result in this part is from a joint work with Julia
Chuzhoy that appeared in SODA 2009.

Finally, we focus on a resource minimization version of the fire
containment problem in a standard mathematical model that is used to
deal with spreading processes of fire and viruses. We show LP-rounding
approximation algorithms for various classes of graphs and provide
essentially tight lower bounds on the integrality gap of natural LP
relaxations for these graph classes. Most results in this part were
presented at SODA 2010 in a joint work with Julia Chuzhoy.

Parinya's advisors are Prof. Janos Simon and Prof. Julia Chuzhoy

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#parinya

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=