Non-independent randomized rounding and an application to digital halftoning

We investigate the problem to round a given [0, 1]-valued matrix to a 0, 1 matrix such that the rounding error with respect to 2 × 2 boxes is small. Such roundings yield good solutions for the digital halftoning prob1em as shown by Asano et al. (SODA 2002). We present a randomized algorithm computing roundings with expected error atmost 0.6287 per box, improving the 0.75 non-constructive bound of Asano et al. Our algorithm is the first one solving this problem fast enough for practical app1ication, name1y in 1inear time. Of a broader interest might be our rounding scheme, which is a modification of randomized rounding. Instead of independently rounding the variables (expected error 0.82944 per box in the worst case), we impose a number of suitable dependencies. Experimental results show that roundings obtained by our approach look much less grainy than by independent randomized rounding, and only slightly more grainy than by error diffusion. On the other hand, the latter algorithm (like all known deterministic algorithms) tends to produce unwanted structures, a problem that randomized algorithms like ours are unlike1y to encounter.