MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Fractional Coloring and Maximum Independent Set

Daniel Vaz
Max-Planck-Institut für Informatik - D1
Probevortrag
AG 1  
AG Audience
English

Date, Time and Location

Friday, 3 June 2016
13:00
30 Minutes
E1 4
333 (Rotunda)
Saarbrücken

Abstract

(Practice talk for CTW 2016)


In this talk, I will present a connection between the Fractional Chromatic Number and the integrality gap of the LP for the Maximum Weight Independent Set. Specifically, the ratio of Fractional Chromatic Number to Clique Number tightly captures the Integrality Gap of the LP with clique constraints for the Maximum Weight Independent Set problem. I will also present immediate applications of our results in approximating the fractional chromatic number of certain classes of intersection graphs.

Contact

Daniel Vaz
--email hidden
passcode not visible
logged in users only

Daniel Vaz, 06/02/2016 13:59 -- Created document.