Tata Institute of Fundamental Research
Approximate Colouring using Semi Definite Programming
Student Seminar
Speaker:
Girish Varma
Date:
Monday, 14 Nov 2011, 16:00 to 17:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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 ).
| Speaker: | Girish Varma |
| Date: | Monday, 14 Nov 2011, 16:00 to 17:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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 ).