Organizers: Patrick Brosnan, Sandra Cerrai, and Vadim Kaloshin
Wednesday @ 3:15pm, Tea 2:45pm - 3:15 pm in room 3201
Math 3206 (Note: For the first part of Fall 2016, this room will be under construction, so the colloquium is temporarily moved to BPS 1250.)
From time to time special colloquia are held on other days, sometimes as part of conferences.
Other special colloquia are the Aziz Lectures and Avron Douglis Memorial Lectures.

Archives: 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017

  • Approximation Algorithms: Some ancient, some new - the good, the bad and the ugly

    Speaker: Samir Khuller (University of Maryland Computer Science ) -

    When: Wed, September 20, 2017 - 3:15pm
    Where: Kirwan Hall 3206

    View Abstract

    Abstract: NP-complete problems abound in every aspect of our daily lives. One approach is to simply deploy heuristics, but for many of these we do not have any idea as to when the heuristic is effective and when it is not. Approximation algorithms have played a major role in the last three decades in developing a foundation for a better understanding of optimization techniques - greedy algorithms, algorithms based on LinearProgramming (LP) relaxations have paved the way for the design of (in some cases) optimal heuristics. Are these the best ones to use in “typical” instances? Maybe, maybe not.

    In this talk we will focus on two specific areas - one is in the use of greedy algorithms for a basic graph problem called connected dominating set, and the other is in the development of LP based algorithms for a basic scheduling problem in the context of data center scheduling.