Abstract: Finding the maximum number of disjoint spanning trees in a given graph is a well-studied problem with several applications and connections. The Tutte-Nash-Williams theorem provides a min-max relation for this problem which also extends to disjoint bases in a matroid and leads to efficient algorithms. Several other packing problems such as element disjoint Steiner trees, disjoint set covers, and disjoint dominating sets are NP-Hard but admit an O(log n)-approximation. Călinescu, Chekuri, and Vondrák viewed all these packing problems as packing bases of a polymatroid and provided a unified perspective. Motivated by applications in wireless networks, recent works have studied the problem of packing set covers in the online model, which poses new challenges for packing problems. Motivated by these applications and theoretical considerations, we formulate an online model for packing bases of a polymatroid and describe a randomized algorithm with a polylogarithmic competitive ratio. For the special case of packing disjoint spanning trees in a graph (or a hypergraph) whose edges arrive online, we provide an alternative to our general algorithm that is simpler and faster while achieving the same poly-logarithmic competitive ratio. The talk will be based on a joint work with Karthekeyan Chandrasekaran and Chandra Chekuri (https://arxiv.org/abs/2503.19999).
Bio: Weihao Zhu is a theory PhD student at Siebel School of Computing and Data Science.