Constructive Algorithms for Discrepancy Minimization

Details Constructive Algorithms for Discrepancy Minimization Constructive Algorithms for Discrepancy Minimization

2010-02-11

arxiv.org/abs/1002.2259v4

Computer Science

Data Structures and Algorithms

Fixed a previous erroneous claim about a logarithmic approximation for hereditary discrepancy. Other minor updates

Scientific paper

Given a set system (V,S), V={1,...,n} and S={S1,...,Sm}, the minimum discrepancy problem is to find a 2-coloring of V, such that each set is colored as evenly as possible. In this paper we give the first polynomial time algorithms for discrepancy minimization that achieve bounds similar to those known existentially using the so-called Entropy Method. We also give a first approximation-like result for discrepancy. The main idea in our algorithms is to produce a coloring over time by letting the color of the elements perform a random walk (with tiny increments) starting from 0 until they reach $-1$ or $+1$. At each time step the random hops for various elements are correlated using the solution to a semidefinite program, where this program is determined by the current state and the entropy method.

Affiliated with

Also associated with

No associations

Rating

Constructive Algorithms for Discrepancy Minimization 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 Algorithms for Discrepancy Minimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructive Algorithms for Discrepancy Minimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67876