View AbstractAbstract: 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.