Recent Progress on Combinatorics and Algorithms for Low Discrepancy Roundings

摘要

Given a [0,1]-valued n-dimensional vector a = (a 1, a 2, . . . , a n ) ∈[0,1] V indexed by a set V = {v 1, v 2, . . . , v n }, we consider the problem of approximating a by a binary (i.e., {0,1}-valued) vector α = (α 1, α 2, . . . , α n ) ∈{0,1} V under the discrepancy measure with respect to a hypergraph $mathcal{H} = (V, mathcal{F})$ . We are interested in the properties of low-discrepancy roundings. Especially, we survey recent works on the combinatorial properties of a global rounding; that is, rounding whose discrepancy is less than 1.