Benjamin Doerr:

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 2x2 boxes is small. Such roundings yield good solutions for the digital halftoning problem as shown by Asano et al. (SODA 2002). We present a randomized algorithm computing roundings with expected error at most 0.5463 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 application, namely in linear time.

Of a broader interest might be our rounding scheme, which is a modification of randomized rounding. Instead of independently rounding the variables, we impose a number of suitable dependencies. Thus by equipping the rounding process with some of the problem information, we reduce the rounding error significantly compared to independent randomized rounding, which leads to an expected error of 0.82944 per box. Finally, we give a characterization of realizable dependencies.

Mathematics Subject Classification (1991): 68W20, 11K38.

Bibliographical note: SIAM Journal on Computing 34 (2004), 299-317.

Keywords: Randomized rounding, discrepancy, digital halftoning

Mail an Jens Burmeister

[Thu Feb 19 18:56:36 2009]

Impressum