School of Technology and Computer Science Seminars
Approximate Colouring using Semi Definite Programming
by Mr. Girish Varma (School of Technology and Computer Science)
Monday, November 14, 2011
from
to
(Asia/Kolkata)
at Colaba Campus ( A-212 (STCS Seminar Room) )
at Colaba Campus ( A-212 (STCS Seminar Room) )
Description |
Determining the chromatic number of a graph is known to be NP-hard. We will consider the problem of coloring a k-colorable graph on n vertices with n^{alpha} colors (where alpha < 1). We will give an algorithm for this problem using Semi Definite Programming (a generalization of LP ). |