|
|
Discrete Mathematics and Optimization Seminar
|
Oct 18th, 2010
|
Constructive Algorithms for Discrepancy Minimization
Nikhil Bansal
IBM TJ Watson
|
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.
|
|
|
|