IC Mondays seminars - Constructive Algorithms for Discrepancy Minimization
Event details
| Date | 15.03.2010 |
| Hour | 16:15 |
| Speaker | Dr. Nikhil Bansal, IBM Hawthorne |
| Location |
INM 202
|
| Category | Conferences - Seminars |
Abstract
The problem of finding the minimum discrepancy coloring is the following: Given a collection of sets S1,...,Sm, color the elements red and blue such that each set is colored as evenly as possible. While several techniques have been developed to show the existence of good colorings, obtaining such colorings algorithmically has been a long standing question.
In this talk, we will describe the first algorithmic results for the problem that essentially match the known existential guarantees. Among other results, we show how to efficiently construct an O(n^{1/2}) discrepancy coloring when m = O(n). This matches the celebrated "six standard deviations suffice" result of Spencer up to constant factors.
Biography
Nikhil Bansal is at the IBM T.J. Watson Research Center, where he currently manages the Algorithms group. His main research interests are in the area of design and analysis of algorithms, with particular focus on approximation and online algorithms for various combinatorial optimization problems. He has over 90 publications in this field and has received the IBM Research best paper award in 2008. He obtained his PhD in 2003 from Carnegie Mellon University, and his Bachelor's degree in 1999 from Indian Institute of Technology, Mumbai.
Links
Practical information
- General public
- Free
Contact
- G.Rochat