Non-independent Randomized Rounding, Linear Discrepancy and an Application to Digital Halftoning

Motivated by an application from image processing (Asano et al., SODA 2002), we investigate the problem to round a given [0; 1]{valued matrix to a 0; 1 matrix such that the L 1 rounding error with respect to all 2 2 boxes is small. We present a randomized algorithm computing roundings with expected error at most 0:5463 per box. Our algorithm is the rst one solving this problem fast enough for practical application, namely in linear time. We use a modi cation of randomized rounding. Instead of independently rounding the variables, we impose a number of suitable dependencies. This reduces the rounding error signi cantly compared to independent randomized rounding, which leads to an expected error of 0.8294 per box. Finally, we give a characterization of realizable dependencies