Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Fractional Coloring and Maximum Independent Set
Speaker:Daniel Vaz
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Probevortrag
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Friday, 3 June 2016
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:333 (Rotunda)
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
Name(s):Daniel Vaz
EMail:ramosvaz@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Daniel Vaz, 06/02/2016 01:59 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Daniel Vaz, 06/02/2016 01:59 PM -- Created document.