Abstract
Cut sparsification of hypergraphs is a widely applied method, where all cuts of a hypergraph H are approximated within 1±ϵ factor by a hypergraph H′ with few hyperedges. It was recently generalized to a setting where the cost of cutting each hyperedge is provided by a given function, that is usually assumed to be submodular.
I will present new bounds for sparsification of submodular hyperedge, including a the first polynomial bound for all submodular functions, and further improvements for various families of submodular functions. I will focus on the common setting, where the sparsifier H′ is a reweighted sub-hypergraph of H, and its size is measured by the number of hyperedges, but will address also a more general notion of representing H' succinctly, where size is measured in bits.
Joint work with Yotam Kenneth.