Abstract:
The
degree bounded network design problem is as follows: given
a graph with connectivity requirement (edge / vertex) between
every pair of vertices and a degree bound for each vertex,
the goal is to find a subgraph satisfying the connectivity
requirement and degree constraint and that the cost should
be as low as possible. Special cases of this include spanning
tree, Steiner tree, Hamiltonian cycle, etc. We will focus
on graphs that satisfy triangle inequality so that edge
splitting-off (replacing edges $xu$ and $xv$ by $uv$) will
not increase the cost.
Biography:
Chan
Yuk Hei obtained his B.Eng in Computer Engineering from
the CUHK in 2007 and is currently an MPhil student in the
Department of Computer Science and Engineering of the CUHK.
His research interest is analysis of LP decoding and its
relation to belief propagation.