[Colloquium] Kim/MS Presentation/Jun 8, 2015

[Margaret Jaffey]

This is an announcement of Hong Kyun (David) Kim's MS Presentation.

------------------------------------------------------------------------------
Date:  Monday, June 8, 2015

Time:  10:00 AM

Place:  Ryerson 277

M.S. Candidate:  Hong Kyun Kim

M.S. Paper Title: On Approximating Node Disjoint Paths in Grids

Abstract:
In the Node-Disjoint Paths problem (NDP), the input is an undirected
$n$-vertex graph $G$, and a collection
$\set{(s_1,t_1),\ldots,(s_k,t_k)}$ of \emph{demand pairs}. The goal is
to route the largest possible number of the demand pairs $(s_i,t_i)$,
by selecting a path connecting each such pair, so that the resulting
paths are node-disjoint. NDP is one of the most basic and extensively
studied routing problems. Unfortunately, its approximability is far
from being well-understood: the best current upper bound of $O(\sqrt
n)$ for NDP is achieved via a simple greedy algorithm, while the best
current lower bound on its approximability is
$\Omega(\log^{1/2-\delta}n)$ for any constant $\delta$. Even for
seemingly simpler special cases, such as planar graphs, and even grid
graphs, no better approximation algorithms are currently known. A
major reason for this impasse is that the standard technique for
designing approximation algorithms for routing problems is LP-rounding
of the standard multicommodity flow relaxation of the problem, whose
integrality gap for NDP is $\Omega(\sqrt n)$ even on grid graphs.

We break the $O(\sqrt{n})$-barrier on the approximation factor for NDP
on grid graphs by providing an $O(n^{1/4}\cdot\log n)$-approximation
algorithm. We distinguish between demand pairs with both vertices
close to the grid boundary, and pairs where at least one of the two
vertices is far from the grid boundary. Our algorithm shows that when
all demand pairs are of the latter type, the integrality gap of the
multicommodity flow LP-relaxation is at most $O(n^{1/4}\cdot \log n)$,
and we deal with demand pairs of the former type by other methods. We
complement our upper bounds by proving that NDP is APX-hard on grid
graphs. Finally we show the extension of the $O(n^{1/4} \cdot \log
n)$-approximation algorithm to EDP on wall graphs. Based on work
advised by Prof. Julia Chuzhoy.

Hong Kyun's advisor is Prof. Laszlo Babai

Login to the Computer Science Department website for details:
 https://www.cs.uchicago.edu/phd/ms_announcements#hongk

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