Constructive Discrepancy Minimization by Walking on The Edges

Details Constructive Discrepancy Minimization by Walking on The Edges Constructive Discrepancy Minimization by Walking on The Edges

2012-03-26

arxiv.org/abs/1203.5747v1

Computer Science

Data Structures and Algorithms

11 pages

Scientific paper

Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer (AMS 1985): In any system of n sets in a universe of size n, there always exists a coloring which achieves discrepancy 6\sqrt{n}. The original proof of Spencer was existential in nature, and did not give an efficient algorithm to find such a coloring. Recently, a breakthrough work of Bansal (FOCS 2010) gave an efficient algorithm which finds such a coloring. His algorithm was based on an SDP relaxation of the discrepancy problem and a clever rounding procedure. In this work we give a new randomized algorithm to find a coloring as in Spencer's result based on a restricted random walk we call "Edge-Walk". Our algorithm and its analysis use only basic linear algebra and is "truly" constructive in that it does not appeal to the existential arguments, giving a new proof of Spencer's theorem and the partial coloring lemma.

Affiliated with

Also associated with

No associations

Rating

Constructive Discrepancy Minimization by Walking on The Edges does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Constructive Discrepancy Minimization by Walking on The Edges, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructive Discrepancy Minimization by Walking on The Edges will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-642618