Abstract
The linear discrepancy problem is to round a given [0,1], [1] – vector x to a binary vector y such that the rounding error with respect to a linear form is small, i.e., such that ‖A(x-y)‖∞ is small for some given matrix A. The discrepancy problem is the special case of x = (1/2, …, 1/2 ). A famous result of Beck and Spencer (1984) as well as Lovász, Spencer and Vesztergombi (1986) shows that the linear discrepancy problem is not much harder than this special case: Any linear discrepancy problem can be solved with at most twice the maximum rounding error among the discrepancy problems of the submatrices of A.
In this paper we strengthen this result for the common situation that the discrepancy of submatrices having n 0 columns is bounded by Cn α0 for some C > 0, α ∈ (0, 1]. In this case, we improve the constant by which the general problem is harder than the discrepancy one, down to 2( 2/3 )α. We also find that a random vector x has expected linear discrepancy 2( 1/2 )α Cn α only. Hence in the typical situation that the discrepancy is decreasing for smaller matrices, the linear discrepancy problem is even less difficult compared to the discrepancy one than assured by the results of Beck and Spencer and Lovász, Spencer and Vesztergombi.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon and J. Spencer. The Probabilistic Method. John Wiley & Sons, Inc., 2nd edition, 2000.
J. Beck and T. Fiala. “Integer making” theorems. Discrete Applied Mathematics, 3:1–8, 1981.
J. Beck and V. T. Sós. Discrepancy theory. In R. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics. 1995.
J. Beck and J. Spencer. Integral approximation sequences. Math. Programming, 30:88–98, 1984.
B. Doerr. Linear and hereditary discrepancy. Combinatorics, Probabilityand Computing, 9:349–354, 2000.
B. Doerr. Lattice approximation and linear discrepancy of totally unimodular matrices. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 119–125, 2001.
B. Doerr and A. Srivastav. Recursive randomized coloring beats fair dice random colorings. In A. Ferreira and H. Reichel, editors, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS) 2001, volume 2010 of Lecture Notes in Computer Science, pages 183–194, Berlin-Heidelberg, 2001. Springer Verlag.
L. Lovász, J. Spencer, and K. Vesztergombi. Discrepancies of set-systems and matrices. Europ. J. Combin., 7:151–160, 1986.
J. Matoušek. Geometric Discrepancy. Springer-Verlag, Berlin, 1999.
J. Matoušek. Tight upper bound for the discrepancy of half-spaces. Discr. & Comput. Geom., 13:593–601, 1995.
J. Matoušek, E. Welzl, and L. Wernisch. Discrepancy and approximations for bounded VC-dimension. Combinatorica, 13:455–466, 1984.
J. Spencer. Six standard deviations suffice. Trans. Amer. Math. Soc., 289:679–706, 1985.
J. Spencer. Randomization, derandomization and antirandomization: Three games. Theor. Comput. Sci., 131:415–429, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Doerr, B. (2002). Typical Rounding Problems. In: Jansen, K., Leonardi, S., Vazirani, V. (eds) Approximation Algorithms for Combinatorial Optimization. APPROX 2002. Lecture Notes in Computer Science, vol 2462. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45753-4_9
Download citation
DOI: https://doi.org/10.1007/3-540-45753-4_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44186-1
Online ISBN: 978-3-540-45753-4
eBook Packages: Springer Book Archive