Optimization algorithms for Carleson and sparse collections of sets

Abstract

Carleson and sparse collections of sets play a central role in dyadic harmonic analysis. We employ methods from optimization theory to study such collections.First, we present a strongly polynomial algorithm to compute the Carleson constant of a collection of sets, improving on the recent approximation algorithm of Rey [6]. Our algorithm is based on submodular function minimization.Second, we provide an algorithm showing that any Carleson collection is sparse, achieving optimal dependence of the respective constants and thus providing a constructive proof of a result of Hänninen [3]. Our key insight is a reformulation of the duality between the Carleson condition and sparseness in terms of the duality between the maximum flow and the minimum cut in a weighted directed graph.