Discrepancy of set-systems and matrices

DOI10.1016/S0195-6698(86)80041-5zbMath0606.05001WikidataQ106026903 ScholiaQ106026903MaRDI QIDQ1084393

J. H. Spencer, Katalin Vesztergombi

Publication date: 1986

Published in: European Journal of Combinatorics (Search for Journal in Brave)

zbMATH Keywords

discrepancy of a set-system

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Related Items (35)

Typical rounding problems ⋮ The smallest n-uniform hypergraph with positive discrepancy ⋮ Approximation-Friendly Discrepancy Rounding ⋮ The continuous Beck-Fiala theorem is optimal ⋮ Balanced two-colorings of finite sets in the cube ⋮ Almost envy-freeness for groups: improved bounds via discrepancy theory ⋮ Matrix approximation and Tusnády's problem ⋮ On combinatorial rectangles with minimum ∞−discrepancy ⋮ Set-Codes with Small Intersections and Small Discrepancies ⋮ Discrepancy theory and related algorithms ⋮ On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems ⋮ The three-permutations problem ⋮ On the discrepancy of random matrices with many columns ⋮ Unnamed Item ⋮ An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound ⋮ On the Computational Complexity of Linear Discrepancy ⋮ Linear discrepancy is \(\Pi_2\)-hard to approximate ⋮ The determinant bound for discrepancy is almost tight ⋮ On Nonnegative Cosine Polynomials with Nonnegative Integral Coefficients ⋮ Non-independent randomized rounding and coloring ⋮ Deterministic discrepancy minimization ⋮ Vector balancing games with aging ⋮ Semidefinite optimization in discrepancy theory ⋮ Unnamed Item ⋮ The Geometry of Differential Privacy: The Small Database and Approximate Cases ⋮ Embedding multidimensional grids into optimal hypercubes ⋮ Better Bin Packing Approximations via Discrepancy Theory ⋮ On the linear and hereditary discrepancies ⋮ A simplified disproof of Beck’s three permutations conjecture and an application to root-mean-squared discrepancy ⋮ On the hereditary discrepancy of homogeneous arithmetic progressions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Vector Balancing Games with Aging ⋮ Algorithmic Aspects of Combinatorial Discrepancy ⋮ On sparse approximations to randomized strategies and convex combinations

Cites Work

• ``Integer-making theorems
• Balanced two-colorings of finite sets in the square. I
• Roth's estimate of the discrepancy of integer sequences is nearly sharp
• Six Standard Deviations Suffice
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Discrepancy of set-systems and matrices