Abstract
Given a [0,1]-valued n-dimensional vector a = (a1, a2, . . . , a n ) ∈[0,1]V indexed by a set V = {v1, v2, . . . , 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Asano, T.: Digital halftoning: algorithm engineering challenges. IEICE Trans. Inf. Syst. E86-D-2, 159–178 (2003)
Asano, T., Katoh, N., Tamaki, H., Tokuyama, T.: The Structure and number of global roundings of a graph. Theor. Comput. Sci. 325(3), 425–437 (2004)
Asano, T., Katoh, N., Tamaki, H., Tokuyama, T.: On geometric structure of global roundings for graphs and range spaces. Proceedings of 9th Scandinavian Workshop on Algorithm Theory (SWAT2004), vol. LNCS 3111, pp. 455–467 (2004)
Asano, T., Katoh, N., Obokata, K., Tokuyama, T.: Matrix rounding under the L p -discrepancy measure and its application to digital halftoning. SIAM J. Comput. 32(6), 1423–1435 (2003)
Asano, T., Matsui, T., Tokuyama, T.: Optimal roundings of sequences and matrices. Nordic J. Comput. 7, 241–256 (2000)
Asano, T., Tokuyama, T.: How to color a checkerboard with a given distribution—matrix rounding achieving low 2 × 2 discrepancy. In: Proceedings of 12th ISAAC, vol. LNCS 2223, pp. 636–648 (2001)
Baranyai, Z.: On the factorization of the complete uniform Hypergraphs, in Infinite and finite sets. In: Hajnal, A., Rado R., Sós, V. T., (eds.) Colloq. Math. Soc. János Bolyai 10, 91–108 (1975)
Beck, J., Sós, V. T.: Discrepancy theory. In: Graham, T., Grötschel, M., Lovász, L. (eds.) Handbook of Combinatorics, vol. II, Elsevier (1995)
Bohus, G.: On the discrepancy of 3 permutations. Random Struct. Algorithms 1, 215–220 (1990)
Chazelle B.: The discrepancy method. Cambridge University Press, Cambridge (2000)
Doerr, B.: Lattice approximation and linear discrepancy of totally unimodular matrices. In: Proceedings of 12th ACM-SIAM Symposium on Discrete Algorithms (SODA2001) pp. 119–125 (2001)
Doerr, B.: Global roundings of sequences. Inf. Proc. Lett. 92-3, 113–116 (2004)
Doerr, B.: Matrix rounding with low error in small submatrices. In: Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms (SODA2005) 1067–1068 (2005)
Doerr, B.: Non-independent randomized rounding and an application to digital halftoning. SIAM J. Comput. 34-2, 299–317 (2004)
Ghouila-Houri, A.: Charactérisation des matrices totalement unimodulaires. C. R. Acad. Sci. Paris 254, 1192–1194 (1962)
Hirokawa, Y.: On discrepancy of optimal rounding of a matrix. Master course dissertation. Tohoku University (in Japanese) (2005)
Jansson J., Tokuyama, T.: Semi-balanced coloring of graphs— 2-colorings based on a relaxed discrepancy condition. Graph Comb. 20-2, 205–222 (2004)
Knuth, D.E.: Tow-way rounding. SIAM J. Discrete Math. 8-2, 281–290 (1995)
Matoušek, J.: Geometric discrepancy. Algorithms and combinatorics, vol. 18, Springer, Heidelberg (1999)
Papadimitriou, C., Steiglitz, K.: Combinatorial optimization, algorithms and complexity. Princeton Hall, Alaska (1982) (New edition, Dover publication 1998)
Rödl, V., Winkler, P.: Concerning a matrix approximation problem. Crux Math. 76–79 (1990)
Sadakane, K., Takki-Chebihi, N., Tokuyama, T.: Combinatorics and algorithms on low-discrepancy roundings of a real sequence. Theor. Comput. Sci. 331-1, 23–36 (2005)
Srinivasan, A.: Improving the discrepancy bound for sparse matrices: better approximations for sparse lattice approximation problems. In: Proceedings of 8th ACM-SIAM Symposium of Discrete Algorithms (SODA1997), pp. 692–701 (1997)
Takki-Chebihi, N.: Global rounding and its application to digital halftoning. doctoral dissertation. Graduate Schools of Information Sciences, Tohoku University, (2004)
Takki-Chebihi, N., Tokuyama, T.: Enumerating roundings for an outerplanar graph. In: Proceedings of 14th International Symposium on Algorithms and Computation (ISAAC2003), vol. LNCS 2906, pp. 425–433 (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tokuyama, T. Recent Progress on Combinatorics and Algorithms for Low Discrepancy Roundings. Graphs and Combinatorics 23 (Suppl 1), 359–378 (2007). https://doi.org/10.1007/s00373-007-0700-9
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s00373-007-0700-9