Description
Abstract: A delta-packing of a set system (X,F) is a sub-collection P of F such that both elements of any pair of PxP are at symmetric difference at least delta. We present an efficient algorithm to compute maximal delta-packings of set systems with finite VC-dimension. Set discrepancy is a basic problem for data approximation and optimization. The goal is to find a 2-coloring of X with minimum discrepancy between the two colors over each set in F. We use our packing algorithm to improve the runtime of algorithms solving set discrepancy in the case of finite VC-dimension set systems.