Loading...
Please wait, while we are loading the content...
Similar Documents
Non-independent Randomized Rounding, Linear Discrepancy and an Application to Digital Halftoning
| Content Provider | CiteSeerX |
|---|---|
| Author | Doerr, Benjamin |
| Abstract | 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. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Linear Discrepancy Digital Halftoning Non-independent Randomized Rounding Image Processing Practical Application Suitable Dependency Modi Cation Linear Time Randomized Rounding Realizable Dependency Randomized Algorithm Independent Randomized Rounding Error Signi |
| Content Type | Text |
