Online Disjoint Spanning Trees and Polymatroid Bases

Chandrasekaran, Karthekeyan; Chekuri, Chandra; Zhu, Weihao

doi:10.4230/LIPIcs.ICALP.2025.44

Online Disjoint Spanning Trees and Polymatroid Bases

Karthekeyan Chandrasekaran

Grainger College of Engineering, University of Illinois, Urbana-Champaign, IL, USA Chandra Chekuri Grainger College of Engineering, University of Illinois, Urbana-Champaign, IL, USA Weihao Zhu Grainger College of Engineering, University of Illinois, Urbana-Champaign, IL, USA

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 [13]. 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 [7, 4]. Călinescu, Chekuri, and Vondrák [2] 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 [11, 6, 1]. The online model poses new challenges for packing problems. In particular, it is not clear how to pack a maximum number of disjoint spanning trees in a graph when edges arrive online. 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. Our algorithm is based on interesting connections to the notion of quotients of a polymatroid that has recently seen applications in polymatroid sparsification [12]. We generalize the previously known result for the online disjoint set cover problem [6] and also address several other packing problems in a unified fashion. 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.

Keywords and phrases:

Disjoint Spanning Trees, Base Packing, Polymatroids, Online Algorithms

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Approximation algorithms analysis ; Theory of computation

\rightarrow

Online algorithms

Related Version:

Full Version: https://arxiv.org/abs/2503.19999 [3]

Funding:

This work was supported in part by NSF grant CCF-2402667.

DOI:

10.4230/LIPIcs.ICALP.2025.44

Event:

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Editors:

Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

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 the maximum number of disjoint bases in a matroid with efficient algorithms [13]. Several other packing problems such as disjoint set covers, disjoint dominating sets, and element disjoint Steiner trees are NP-Hard but admit an $O(\log{n})$ -approximation¹¹1We are using the convention of $\alpha$ -approximation for a maximization problem with $\alpha>1$ with the understanding that the returned value is at least $\texttt{opt}/\alpha$ . [7, 4]. Călinescu, Chekuri, and Vondrák [2] viewed these 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 [11, 6, 1]. The online model poses new challenges for packing problems. In particular, it is not clear how to pack a maximum number of disjoint spanning trees in a graph when edges arrive online. Motivated by these applications and theoretical considerations we consider the problem of packing disjoint bases of a polymatroid in the online model.

A polymatroid $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ on a ground set $\mathcal{N}$ is an integer-valued monotone submodular function with $f(\emptyset)=0$ . We recall that a function $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ is monotone if $f(A)\leq f(B)$ for every $A\subseteq B$ and submodular if $f(A)+f(B)\geq f(A\cup B)+f(A\cap B)$ for every $A,B\subseteq\mathcal{N}$ . A subset $S\subseteq\mathcal{N}$ is a base of $f$ if $f(S)=f(\mathcal{N})$ .²²2In most settings, one would define a set $S$ to be a base if it is inclusionwise minimal subject to satisfying $f(S)=f(\mathcal{N})$ . This is particularly important in the setting of matroids where all bases have the same cardinality which is not necessarily true in the polymatroidal setting. However, since we are interested in (approximating) the maximum number of disjoint bases we adopt the relaxed definition for simplicity. In the Disj-Polymatroid-Bases problem, we are given a polymatroid $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ via an evaluation oracle. The goal is to find a maximum number of disjoint bases. We define

\texttt{opt}(f):=\max\{k:\exists\ k\text{ disjoint bases of $f$}\}.

Polymatroids generalize matroid rank function, coverage functions, and many others. Consequently, numerous set packing problems can be cast as special cases of Disj-Polymatroid-Bases. We will discuss some of these special cases shortly.

Online Disj-Polymatroid-Bases Model.

We formally describe the online model for Disj-Polymatroid-Bases (denoted Online-Disj-Polymatroid-Bases). We have an underlying polymatroid $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ over a large but finite ground set ${\mathcal{N}}$ . Let $n:=|{\mathcal{N}}|$ . We index the elements of the ground set $\mathcal{N}$ as $e_{1},e_{2},\ldots,e_{n}$ where $e_{t}$ is the element that arrives at time $t$ for every $t\in[n]$ . For each $t\in[n]$ , we denote $\mathcal{N}_{t}:=\{e_{1},e_{2},\ldots,e_{t}\}$ and let $f_{|{\mathcal{N}}_{t}}:2^{{\mathcal{N}}_{t}}\rightarrow\mathbb{Z}_{\geq 0}$ be the function obtained from $f$ by restricting the ground set to ${\mathcal{N}}_{t}$ , that is, $f_{|{\mathcal{N}}_{t}}(A):=f(A)$ for every $A\subseteq{\mathcal{N}}_{t}$ . At each timestep $t\in[n]$ , the online algorithm has access to the evaluation oracle³³3The evaluation oracle of a function $g:2^{V}\rightarrow\mathbb{R}$ takes a set $S\subseteq V$ as input and returns $g(S)$ . of the function restricted to the set of elements that have arrived until time $t$ , i.e., the evaluation oracle of the function $f_{|{\mathcal{N}}_{t}}$ , and has to color element $e_{t}$ irrevocably. A color is said to be a base color if the set $S$ of elements with that color is a base of $f$ . The goal of the online algorithm is to maximize the number of base colors. We remark that we are implicitly assuming that the elements of ${\mathcal{N}}$ is the input sequence. The competitive ratio of an online algorithm is the ratio between the base colors in an optimal offline algorithm and that of the online algorithm. For randomized online algorithms, we will be interested in the expected competitive ratio. We assume that the online algorithm has prior knowledge of the function value of the ground set ${\mathcal{N}}$ , i.e., $f({\mathcal{N}})$ . This assumption is motivated by applications to be discussed below.

Applications.

Polymatroids generalize coverage functions and matroid rank functions. We discuss these two special cases, the associated packing problems, and their online model below.

1.

In the Disj-Set-Cover problem, the input is a set system over a finite universe. We will alternatively view the set system as a hypergraph $H=(V,E)$ where $V$ corresponds to the universe and the hyperedges in $E$ correspond to sets in the system. The goal is to find a maximum number of disjoint set covers (a subset $A\subseteq E$ of hyperedges is a set cover if $\cup_{e\in A}e=V$ ). Disj-Set-Cover can be cast as a special case of Disj-Polymatroid-Bases by considering the coverage function of the hypergraph as the polymatroid, i.e., by considering the polymatroid $f:2^{E}\rightarrow\mathbb{Z}_{\geq 0}$ defined as $f(A):=|\cup_{e\in A}e|$ . Coverage functions are fairly general with several prominent special cases–e.g., the domatic number problem is a special case of Disj-Set-Cover [7]. In the online setting of Disj-Set-Cover (termed Online-Disj-Set-Cover), the vertex set is known in advance while the hyperedges are revealed in an online fashion. The online algorithm has to color each hyperedge immediately upon arrival irrevocably in order to maximize the number of colors that form a set cover.
2.

In the Disj-Matroid-Bases problem, we are given evaluation access to a matroid rank function $r:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ over a ground set ${\mathcal{N}}$ (we recall that a matroid rank function $r$ is a polymatroid that additionally satisfies $r(\{e\})\leq 1$ for every $e\in{\mathcal{N}}$ ). A subset $S\subseteq{\mathcal{N}}$ is a base of the matroid if $r(S)=r({\mathcal{N}})$ . The goal is to find a maximum number disjoint bases of the matroid. Matroid rank function is a polymatroid and hence, Disj-Matroid-Bases is a special case of Disj-Polymatroid-Bases. In the online setting of Disj-Matroid-Bases (termed Online-Disj-Matroid-Bases), the ground set is revealed in an online fashion while the online algorithm has access to the rank function restricted to the set of elements that have arrived so far. The online algorithm has to color each element immediately upon arrival irrevocably in order to maximize the number of base colors.

Next, we describe three special cases of Disj-Polymatroid-Bases, namely Disj-Matrix-Bases, Disj-Spanning-Trees, and Disj-Conn-Spanning-Subhypergraphs. To the best of authors’ knowledge, these three problems have not been explored in the online setting. One of the motivations of this work is to understand these three problems in the online setting.

1.

In the Disj-Matrix-Bases problem, we are given a matrix $M\in\mathbb{R}^{n\times d}$ of rank $d$ and the goal is to find a maximum number of disjoint spanning subsets of row-vectors – a subset of row vectors is spanning if its linear hull is $\mathbb{R}^{d}$ . This is a special case of Disj-Matroid-Bases where the matroid is the linear matroid defined by $M$ (and consequently, the rank function of a subset of row-vectors is the dimension of the subspace spanned by them). In the online setting of Disj-Matrix-Bases (termed Online-Disj-Matrix-Bases), the rows of the matrix are revealed in an online fashion and the online algorithm has to color each row immediately upon arrival irrevocably in order to maximize the number of spanning colors.
2.

In the Disj-Spanning-Trees problem, we are given a connected graph $G=(V,E)$ and the goal is to find a maximum number of disjoint spanning trees in $G$ . Disj-Spanning-Trees is a special case of Disj-Matroid-Bases where the matroid is the graphic matroid defined by $G$ (and consequently, the rank function of a subset $F\subseteq E$ is $|V|-c(V,F)$ , where $c(V,F)$ is the number of components in the graph $(V,F)$ ). In the online setting of Disj-Spanning-Trees (termed Online-Disj-Spanning-Trees), the vertex set of $G$ is known in advance while the edges of $G$ are revealed in an online fashion and the online algorithm has to color each edge immediately upon arrival irrevocably in order to maximize the number of connected colors – a color is connected if the edges of the color form a connected graph over the vertex set $V$ .
3.

In the Disj-Conn-Spanning-Subhypergraphs problem, we are given a connected hypergraph $H=(V,E)$ and the goal is to find a maximum number of disjoint connected spanning subhypergraphs in $H$ . Disj-Conn-Spanning-Subhypergraphs is a special case of Disj-Polymatroid-Bases where the polymatroid $f:2^{E}\rightarrow\mathbb{Z}_{\geq 0}$ of interest is defined as $f(A):=|V|-c(V,A)$ for every $A\subseteq E$ , where $c(V,A)$ is the number of components in the hypergraph $(V,F)$ . Disj-Conn-Spanning-Subhypergraphs arises in the context of packing element-disjoint Steiner trees [4]. In the online setting of Disj-Conn-Spanning-Subhypergraphs (termed Online-Disj-Conn-Spanning-Subhypergraphs), the vertex set of $G$ is known in advance while the hyperedges of $G$ are revealed in an online fashion and the online algorithm has to color each hyperedge immediately upon arrival irrevocably in order to maximize the number of connected colors – a color is connected if the hyperedges of the color form a connected hypergraph over the vertex set $V$ .

Disj-Conn-Spanning-Subhypergraphs generalizes Disj-Spanning-Trees (in both offline and online settings): if the input hypergraph is a graph, then the problem corresponds to Disj-Spanning-Trees. Disj-Conn-Spanning-Subhypergraphs is also closely related to Disj-Set-Cover in the following sense: both problems are defined over hypergraphs – the latter asks for disjoint spanning subhypergraphs (which is equivalent to disjoint set covers) while the former asks for disjoint connected spanning subhypergraphs. Disj-Conn-Spanning-Subhypergraphs generalizes Disj-Set-Cover (in both offline and online settings) via the following approximation-preserving reduction from the latter to the former: given an instance $H=(V,E)$ of Disj-Set-Cover, add a new vertex $r$ and stretch every hyperedge of $H$ to include $r$ to obtain a new hypergraph $H^{\prime}=(V+r,E^{\prime})$ ; the maximum number of disjoint set covers in $H$ is equal to the maximum number of disjoint connected spanning subhypergraphs in $H^{\prime}$ .

Prior work in the offline setting.

Disj-Matroid-Bases is polynomial-time solvable [5]. Disj-Set-Cover and Disj-Conn-Spanning-Subhypergraphs are $o(\log|V|)$ -inapproximable and $O(\log|V|)$ -approximable [7, 4]. Călinescu, Chekuri, and Vondrák [2] introduced Disj-Polymatroid-Bases as a unified generalization of Disj-Matroid-Bases, Disj-Set-Cover, and Disj-Conn-Spanning-Subhypergraphs. They designed an $O(\log{f({\mathcal{N}})})$ -approximation for Disj-Polymatroid-Bases by showing an approximate min-max relation for $\texttt{opt}(f)$ . Their approximate min-max relation is based on the following minimization problem:

k^{*}(f):=\min_{A\subseteq{\mathcal{N}}:\ f(A)<f({\mathcal{N}})}\left\lfloor% \frac{\sum_{e\in{\mathcal{N}}}(f(A+e)-f(A))}{f({\mathcal{N}})-f(A)}\right\rfloor.

It is easy to see that $\texttt{opt}(f)\leq k^{*}(f)$ (e.g., see [2]). Moreover, if the polymatroid $f$ is a matroid rank function, then Edmonds [5] showed that $\texttt{opt}(f)=k^{*}(f)$ . Edmonds’ result is constructive and implies a polynomial time algorithm for Disj-Matroid-Bases. However, for coverage functions, it is known that $\texttt{opt}(f)\leq(1+o(1))k^{*}(f)/\log{f({\mathcal{N}})}$ [7]. Călinescu, Chekuri, and Vondrák showed that this bound is tight by giving a polynomial-time algorithm to construct $(1-o(1))k^{*}(f)/\log{f({\mathcal{N}})}$ disjoint bases (and hence, $\texttt{opt}(f)\geq(1-o(1))k^{*}(f)/\log{f({\mathcal{N}})}$ ). Their algorithm unifies the approximation algorithms for Disj-Set-Cover [7] and Disj-Conn-Spanning-Subhypergraphs [4]. We state their algorithm since it will be important for the rest of our discussion: The algorithm computes the parameter $k:=\lfloor k^{*}(f)/(\log{f({\mathcal{N}})}+\log{\log{f({\mathcal{N}})}})\rfloor$ (by guessing/binary search) and colors each element with a uniformly random color chosen from a color palette of size $k$ . Călinescu, Chekuri, and Vondrák showed that the expected number of base colors returned by this random coloring algorithm is at least $(1-e/\log{f({\mathcal{N}})})k=(1-o(1))k^{*}(f)/\log{f({\mathcal{N}})}$ . An alternative algorithm based on a random permutation is also described in [2] that we discuss later.

Prior work in the online setting.

Online-Disj-Set-Cover was introduced and studied by Pananjady, Bagaria, and Vaze [11] driven by applications to sensor networks, supply chain management, and crowd-sourcing platforms. In the context of Disj-Set-Cover, the quantity $k^{*}(f)$ associated with the coverage function $f$ of the hypergraph $H=(V,E)$ has a simple interpretation: it is equal to the min-degree of the hypergraph $H$ . Pananjady, Bagaria, and Vaze showed that if the min-degree is known to the online algorithm in advance, then there is an online deterministic algorithm with competitive ratio $O(\log{n})$ , where $n$ is the number of vertices in the input hypergraph; we note that a randomized online algorithm with the same competitive ratio is an easy consequence of the random coloring algorithm of [2] discussed above. On the lower bound side, they showed that if min-degree is not known in advance, then every online deterministic algorithm for Disj-Set-Cover has competitive ratio $\Omega(n)$ . Although this lower bound result seems to suggest that knowing the min-degree of the graph in advance is required to achieve any meaningful competitive ratio, two different results have overcome this seeming technical barrier by empowering the online algorithm in other ways: Firstly, Emek, Goldbraikh, and Kantor [6] designed an online randomized algorithm with expected competitive ratio $O(\log^{2}{n})$ (assuming no knowledge of the min-degree but using randomness). On the lower bound side, they showed that every online randomized algorithm has expected impure competitive ratio⁴⁴4An online (randomized) algorithm for Disj-Set-Cover has impure competitive ratio $\alpha$ if the (expected) number of set covers in the online algorithm is at least $(\texttt{opt}(H)/\alpha)-\beta$ for some $\beta>0$ that is a function only of $n$ , where $H$ is the input hypergraph, $n$ is the number of vertices in $H$ , and $\texttt{opt}(H)$ is the maximum number of disjoint set covers in $H$ . Our work focuses on the case of $\beta=0$ , i.e., pure competitive ratio. $\Omega(\log{n}/\log{\log{n}})$ (even with knowledge of min-degree). Secondly, Bienkowski, Byrka, and Jeż [1] designed an online deterministic algorithm with impure competitive ratio $O(\log^{2}{n})$ (assuming no knowledge of the min-degree but settling for impure competitive ratio).

For the more general problem of Online-Disj-Polymatroid-Bases, Pananjady, Bagaria, and Vaze [11] observed that if $k^{*}(f)$ is known in advance, then it is possible to design a randomized online algorithm with expected competitive ratio $O(\log{f({\mathcal{N}})})$ : indeed, the random coloring algorithm of [2] mentioned above can be implemented in the online setting using knowledge of $k^{*}(f)$ and it will have the stated competitive ratio (via the results of [2]). In this work, we are interested in Online-Disj-Polymatroid-Bases in the setting where $k^{*}(f)$ is not known in advance.

Our motivations to consider Online-Disj-Polymatroid-Bases are multifold: Disj-Matrix-Bases and Disj-Spanning-Trees are fundamental problems in linear algebra and graph algorithms respectively. We note that Disj-Matrix-Bases in the online arrival model is non-trivial even for $2$ -dimensional vectors, i.e., for $d=2$ . Disj-Conn-Spanning-Subhypergraphs generalizes Disj-Spanning-Trees and arises in the context of packing element-disjoint Steiner trees [4]. As mentioned earlier, Disj-Conn-Spanning-Subhypergraphs can also be viewed as a generalization of Disj-Set-Cover. Although Disj-Set-Cover has been studied in the online model, there has not been any work on Disj-Conn-Spanning-Subhypergraphs in the online model.

1.1 Our Results

Throughout this work, we will denote the color palette by the set of natural numbers. There is a natural greedy algorithm for Online-Disj-Polymatroid-Bases: initialize color $c=1$ ; at each timestep $t\in[n]$ : use color $c$ for element $e_{t}$ and if the set of elements with color $c$ is a base, then increment $c$ . For uniform random arrival order, the competitive ratio of this simple online algorithm is $O(\log{f({\mathcal{N}})})$ (via the results of [2]); this does not seem to have been explicitly noted in prior work. For arbitrary arrival order, the competitive ratio of this online algorithm is $k^{*}(f)$ : the algorithm will return at least one base while the maximum number of possible bases is at most $k^{*}(f)$ (since $\texttt{opt}(f)\leq k^{*}(f)$ ). It is known that $k^{*}(f)$ is the best possible competitive ratio of deterministic online algorithms that do not have prior knowledge of $k^{*}(f)$ [11]. In this work, we are interested in the setting of arbitrary arrival order without prior knowledge of $k^{*}(f)$ . For this setting, we design a randomized online algorithm with expected competitive ratio $O(\log^{2}{f({\mathcal{N}})})$ .

Theorem 1.

For Disj-Polymatroid-Bases, there exists a randomized online algorithm with expected competitive ratio $O(\log^{2}{f({\mathcal{N}})})$ . The runtime of the algorithm at each timestep $t\in[n]$ is $poly(t,\log{f({\mathcal{N}})})$ .

We recall that the best-known approximation factor for Disj-Polymatroid-Bases in the offline setting is $O(\log{f({\mathcal{N}})})$ , and hence the competitive ratio of our online algorithm nearly matches that of the best possible offline algorithm. We discuss the consequences of Theorem 1 for the applications. Specializing Theorem 1 to coverage functions implies a randomized online algorithm for Disj-Set-Cover with expected competitive ratio $O(\log^{2}{n})$ , where $n$ is the number of vertices of the input hypergraph, thus recovering the result of [6]. Specializing Theorem 1 to matroid rank functions implies a randomized online algorithm for Disj-Matroid-Bases with expected competitive ratio $O(\log^{2}{r})$ , where $r$ is the rank of the ground set. Consequently, we obtain a randomized online algorithm with expected competitive ratio $O(\log^{2}{d})$ for Disj-Matrix-Bases where $d$ is the dimension of the span of the input vectors and with expected competitive ratio $O(\log^{2}{n})$ for Disj-Spanning-Trees where $n$ is the number of vertices of the input graph. Specializing Theorem 1 to the polymatroid function that arises in Disj-Conn-Spanning-Subhypergraphs implies a randomized online algorithm for Disj-Conn-Spanning-Subhypergraphs with expected competitive ratio $O(\log^{2}{n})$ , where $n$ is the number of vertices of the input hypergraph.

Our randomized online algorithm to prove Theorem 1 is based on the notion of quotients of a polymatroid. Quotients played a central role in the recent result on polymatroidal sparsification [12]. The competitive ratio analysis of our algorithm is based on novel properties of quotients which might be of independent interest. We prove Theorem 1 in two steps: firstly, we design a randomized online algorithm with competitive ratio $O(\log^{2}{f({\mathcal{N}})})$ but as stated it needs to solve an NP-Hard problem. Next, we modify this algorithm to achieve polynomial run-time while achieving the same competitive ratio. For this, we rely on the strength decomposition of polymatroids which is computable in polynomial time and show a property connecting the strength decomposition to min-sized quotients. Although these algorithms are general and powerful, they are computationally expensive and difficult to interpret for specific applications. As our second result, we give a very simple and fast online randomized algorithm for Disj-Conn-Spanning-Subhypergraphs and Disj-Spanning-Trees that achieves the same competitive ratio.

Theorem 2.

For Disj-Conn-Spanning-Subhypergraphs, there exists a randomized online algorithm with competitive ratio $O(\log^{2}n)$ , where $n$ is number of vertices in the input hypergraph. The runtime of the algorithm at each timestep $t$ is $O(|e_{t}|^{2})$ , where $e_{t}$ is the hyperedge that arrives at time $t$ . In particular, the algorithm for Disj-Spanning-Trees can be implemented to run in constant time at each timestep.

1.2 Technical Background and Overview of Algorithms

We recall that we assume $\mathcal{N}$ is the input sequence. Let $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ be the polymatroid of interest. Let $r:=f(\mathcal{N})$ be the function value of bases and $k^{*}:=k^{*}(f)$ . For the discussion here, we will assume that $f(e)>0$ for every $e\in{\mathcal{N}}$ , $r\geq 2$ , and $k^{*}=\Omega(\log^{2}r)$ since this is the non-trivial case. First consider the setting where the online algorithm knows $k^{*}$ in advance. In this setting, coloring each element uniformly from the palette $[\Theta(k^{*}/\log r)]$ gives $\Omega(k^{*}/\log{r})$ base colors in expectation and, consequently achieves $O(\log{r})$ -competitive ratio.

Suppose $k^{*}$ is not known in advance. Our approach is to estimate $k^{*}$ at each timestep. At each timestep $t\in[n]$ , suppose that we can find a number $q_{t}$ that is within a $\text{poly}(r)$ factor of $k^{*}$ , i.e., $q_{t}\in[\frac{k^{*}}{\text{poly}(r)},k^{*}\cdot\text{poly}(r)]$ – we call such a $q_{t}$ as a coarse estimate. Let $P_{t}$ be a uniform random sample from $\{q_{t}\cdot 2^{-O(\log r)},\ldots,q_{t}\cdot 2^{-1},q_{t}\cdot 2^{0},q_{t}% \cdot 2^{1},\ldots,q_{t}\cdot 2^{O(\log r)}\}$ ; $P_{t}$ is a $2$ -approximation of $k^{*}$ with probability $\Omega(1/\log r)$ . Consequently, coloring the element $e_{t}$ uniformly from the palette $[\Theta(P_{t}/\log^{2}r)]$ leads to $\Omega(k^{*}/\log^{2}r)$ base colors in expectation.

The key challenge is computing a coarse estimate for $k^{*}$ which depends on the full input sequence. This may not be feasible at all timesteps owing to the limited knowledge of the polymatroid. Instead, we compute an estimate at each timestep such that the elements at timesteps which achieve the coarse property provide a sufficiently large value of $k^{*}$ . We formalize this approach now. Suppose we have a subroutine to compute some estimate $q_{t}$ at each timestep $t\in[n]$ . We call a timestep $t\in[n]$ to be good if the estimate $q_{t}$ is a coarse estimate of $k^{*}$ and bad otherwise. We let $\mathcal{N}_{\mathsf{good}}$ be the collection of elements that arrive at good timesteps and focus on the function $f$ restricted to ${\mathcal{N}}_{\mathsf{good}}$ , i.e., on the function $g:=f_{|{\mathcal{N}}_{\mathsf{good}}}$ . Suppose that the following two properties hold: (i) Bases of $g$ are also bases of $f$ and (ii) $k^{*}(g)=\Omega(1)k^{*}$ . These two properties suffice to obtain $\Omega(k^{*}/\log^{2}{r})$ base colors in expectation via the fine-tuned random coloring argument in the previous paragraph.

We rely on the notion of quotients to obtain an estimator satisfying properties (i) and (ii).

Definition 3.

For a polymatroid $h:2^{\mathcal{V}}\rightarrow\mathbb{Z}_{\geq 0}$ , a set $Q\subseteq\mathcal{V}$ is a quotient of $h$ if $h(e+(\mathcal{V}\setminus Q))>h(\mathcal{V}\setminus Q)$ $\forall e\in Q$ , i.e., if each element $e\in Q$ has strictly positive marginal with respect to $\mathcal{V}\setminus Q$ .

See Appendix A for the interpretation of quotients for some concrete polymatroids. We observed that the minimum size of a non-empty quotient of $f$ is an $r$ -approximation of $k^{*}$ – see Appendix B. This inspired us to use the minimum-sized quotient of $f_{|{\mathcal{N}}_{t}}$ that contains $e_{t}$ as the estimate at each timestep $t\in[n]$ . That is, we use the estimator defined as

\displaystyle q_{t}

\displaystyle:=\min\{|Q|:e_{t}\in Q\subseteq\mathcal{N}_{t}\text{ and $Q$ is a% quotient of $f_{|\mathcal{N}_{t}}$}\}.

(1)

Our main technical contribution is showing that the preceding estimator satisfies the two properties that we discussed earlier. This result combined with the random coloring process yields the desired $O(\log^{2}r)$ -competitive ratio. A technical issue is that the estimator $q_{t}$ is NP-Hard to compute for general polymatroids (even for matroid rank functions). However, we note that a $\text{poly}(r)$ -approximation of $q_{t}$ is sufficient for the desired competitive ratio. We show that an $r$ -approximation of $q_{t}$ can be computed using a strength decomposition with respect to $f_{|\mathcal{N}_{t}}$ which admits a polynomial-time algorithm.

We briefly discuss the idea behind the simpler algorithm for Disj-Conn-Spanning-Subhypergraphs and Disj-Spanning-Trees of Theorem 2. We will focus on Disj-Spanning-Trees here. The polymatroid $f:2^{E}\rightarrow\mathbb{Z}_{\geq 0}$ of interest here is the rank function of the graphic matroid defined by the undirected graph $G=(V,E)$ . For this case, the quotient computation is polynomial-time solvable since $q_{t}$ is equal to the min $u_{t}$ - $v_{t}$ cut value in the graph $(V,E_{t})$ where $e_{t}=(u_{t},v_{t})$ and $E_{t}=\{e_{1},e_{2},\ldots,e_{t}\}$ . However, we show that a much simpler estimator for Disj-Spanning-Trees also achieves properties (i) and (ii) mentioned above: we use

\eta_{t}:=\text{number of edges between $u_{t}$ and $v_{t}$ in the graph $(V,E% _{t})$}.

This estimator generalizes also to Disj-Conn-Spanning-Subhypergraphs.

Organization.

In Section 2, we set up the notation and mention certain properties of polymatroids. In Section 3, we present a randomized online algorithm with competitive ratio $O(\log^{2}r)$ , where the run-time per timestep is exponential. In Section 4, we show how to achieve the same competitive ratio in polynomial time per timestep thereby proving Theorem 1. In Section 5, we show a simple online randomized algorithm for Disj-Conn-Spanning-Subhypergraphs thereby proving Theorem 2. Due to space limitations, certain proofs are deferred to the full version [3].

2 Preliminaries

Given two integers $a\leq b$ , let $[a,b]$ denote the set of integers $x$ with $a\leq x\leq b$ and $[b]$ denote the set of integers $x$ with $1\leq x\leq b$ . The $\log(\cdot)$ operator with an unspecified base refers to $\log_{2}(\cdot)$ . We recall that a polymatroid is an integer-valued monotone submodular function with its value on the empty set being $0$ . Let $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ be a polymatroid. We denote the value of the function $f$ on the ground set ${\mathcal{N}}$ by $r:=f(\mathcal{N})$ and recall that a set $S\subseteq{\mathcal{N}}$ is a base if $f(S)=r$ . We will assume that $f(e)>0$ for every element $e\in{\mathcal{N}}$ : if we have an element $e\in{\mathcal{N}}$ with $f(e)=0$ , then $f(S)=f(S+e)$ for every $S\subseteq{\mathcal{N}}$ by submodularity and consequently, picking an arbitrary color for $e$ does not influence the number of base colors.

For a subset $A\subseteq\mathcal{N}$ , we define the marginal function with respect to $A$ as the function $f_{A}:2^{\mathcal{N}}\rightarrow\mathbb{Z}$ defined by $f_{A}(S):=f(A\cup S)-f(A)$ for every $S\subseteq\mathcal{N}$ . If $f$ is submodular, then the function $f_{A}$ is also submodular for every $A\subseteq\mathcal{N}$ . For ease of notation, for an element $e\in\mathcal{N}$ , we let $e$ denote the singleton set $\{e\}$ . For every set $S\subseteq\mathcal{N}$ , we use $S+e$ and $S-e$ to abbreviate $S\cup\{e\}$ and $S\setminus\{e\}$ , respectively.

We need the notion of span, closed sets, and quotients. For a set $S\subseteq\mathcal{N}$ , the span of $S$ is the set of elements with marginal value $0$ with respect to $S$ , i.e., $\text{span}(S):=\{e\in\mathcal{N}:f_{S}(e)=0\}$ . We note that for every two sets $A\subseteq B$ , $\text{span}(A)\subseteq\text{span}(B)$ since $f$ is a monotone submodular function. A set $S\subseteq\mathcal{N}$ is closed if $S=\text{span}(S)$ . A set $Q\subseteq\mathcal{N}$ is a quotient of $f$ if $Q=\mathcal{N}\setminus\text{span}(S)$ for some set $S\subseteq\mathcal{N}$ . This definition of quotient is equivalent to the one in Definition 3. We note that the empty set is closed (since $f(e)>0$ for every element $e\in\mathcal{N}$ ) which implies that $\mathcal{N}$ is a quotient of $f$ . The notion of quotients plays a central role in polymatroid sparsification [12].

For a set $S\subseteq\mathcal{N}$ , let $f_{|S}:2^{S}\rightarrow\mathbb{Z}_{\geq 0}$ be the function obtained from $f$ by restricting the ground set to $S$ , i.e., $f_{|S}(T):=f(T)$ for every $T\subseteq S$ . We recall that if $f$ is a polymatroid, then $f_{|S}$ is also a polymatroid for every $S\subseteq{\mathcal{N}}$ . Restricting the ground set preserves quotients as shown in the following lemma.

Lemma 4 ([12]).

Let $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ be a polymatroid. Let $Q$ be a quotient of $f$ and $S\subseteq\mathcal{N}$ . Then, $Q\cap S$ is a quotient of $f_{|S}$ .

We recall that

	$\displaystyle\texttt{opt}(f)$	$\displaystyle=\max\{k:\ \exists k\text{ disjoint bases of }f\}\ \text{and}$
	$\displaystyle k^{*}(f)$	$\displaystyle=\min_{A\subseteq\mathcal{N}:f(A)<f(\mathcal{N})}\left\lfloor% \frac{\sum_{e\in\mathcal{N}}f_{A}(e)}{f(\mathcal{N})-f(A)}\right\rfloor.$		(2)

We note that there exists a closed set $A$ that achieves the minimum in the definition of $k^{*}(f)$ : suppose $A$ is a set that achieves the minimum, then $f(\text{span}(A))=f(A)<f({\mathcal{N}})$ by definition of span while $\sum_{e\in\mathcal{N}}f_{A}(e)\geq\sum_{e\in\mathcal{N}}f_{\text{span}(A)}(e)$ by submodularity of function $f$ and consequently, $\lfloor\frac{\sum_{e\in\mathcal{N}}f_{A}(e)}{f(\mathcal{N})-f(A)}\rfloor\geq% \lfloor\frac{\sum_{e\in\mathcal{N}}f_{\text{span}(A)}(e)}{f(\mathcal{N})-f(% \text{span}(A))}\rfloor$ . If the function $f$ is clear from context, then we denote $\texttt{opt}(f)$ and $k^{*}(f)$ by opt and $k^{*}$ respectively. We need the following approximate min-max relation between opt and $k^{*}$ .

Theorem 5 ([2]).

$\frac{k^{*}}{O(\log r)}\leq\texttt{opt}\leq k^{*}$ .

We need the following lemma showing that for every polymatroid $f$ , sampling each element independently with probability $\Omega\left(\frac{c\cdot\log r}{k^{*}}\right)$ gives a base of $f$ with constant probability. A variant of the lemma was shown in [2]. We include a proof of the lemma in Appendix C for completeness.

Lemma 6.

Let $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ be a polymatroid with $f(\mathcal{N})=r\geq 2$ . Let $p:=\min\{1,\frac{2\log r}{k^{*}}\}$ and $S\subseteq\mathcal{N}$ be a subset obtained by picking each element in $\mathcal{N}$ with probability at least $p$ independently at random. Then, $S$ is a base of $f$ with probability at least $\frac{1}{2}$ .

We recall that the elements of the ground set ${\mathcal{N}}$ are indexed as $e_{1},e_{2},\ldots,e_{n}$ according to the arrival order, i.e., $e_{t}$ is the element that arrives at time $t\in[n]$ and moreover, ${\mathcal{N}}_{t}=\{e_{1},e_{2},\ldots,e_{t}\}$ is the set of elements that have arrived until time $t$ for every $t\in[n]$ . For a coloring of all elements, we say that a fixed color is a base color if the set of elements of that color is a base of the polymatroid $f$ . Let $\texttt{Alg}(f)$ be the number of base colors obtained by an online algorithm Alg for a given polymatroid $f$ . A deterministic online algorithm Alg is (purely) $\alpha$ -competitive if for every polymatroid $f$ , we have

\texttt{Alg}(f)\geq\frac{\texttt{opt}(f)}{\alpha}.

(3)

A randomized online algorithm is $\alpha$ -competitive if the bound in (3) holds in expectation.

3 An $O(\log^{2}r)$ -Competitive Algorithm

In this section, we present a randomized online algorithm with expected competitive ratio $O(\log^{2}r)$ but the run-time of the algorithm at each timestep will be exponential. The purpose of this section is to illustrate that the online arrival order has sufficient information to achieve a reasonable competitive ratio (albeit in exponential runtime) and to highlight the main ideas underlying the eventual polynomial-time algorithm that will prove Theorem 1. We describe the algorithm in Section 3.1. We present a novel property of the sequence of minimum sized quotients containing the last element with respect to a fixed ordering in Section 3.2. We prove the structural property that focusing on elements whose estimates are within a $\text{poly}(r)$ factor of $k^{*}$ does not decrease $k^{*}$ by more than a constant factor in Section 3.3. We use these properties to analyze the competitive ratio of the algorithm in Section 3.4. For Sections 3.1, 3.2, 3.3, and 3.4, we assume that $r\geq 2$ and $k^{*}\geq 120\log^{2}r$ . We discuss how to relax the assumption in Section 3.5 in which we combine the designed algorithm with algorithms for other cases to obtain an algorithm with competitive ratio $O(\log^{2}r)$ . We will modify the algorithm in Section 4 to design an $O(\log^{2}r)$ -competitive algorithm that runs in polynomial time at each timestep, thereby completing the proof of Theorem 1.

3.1 Algorithm Description

We assume that $k^{*}\geq 120\log^{2}r$ and $r\geq 2$ . The algorithm proceeds as follows: At each timestep $t\in[n]$ , the algorithm computes

q_{t}:=\min\{|Q|:e_{t}\in Q\subseteq\mathcal{N}_{t}\text{ and $Q$ is a % quotient of $f_{|\mathcal{N}_{t}}$}\}.

We note that $\mathcal{N}_{t}$ is a quotient of $f_{|\mathcal{N}_{t}}$ with $e_{t}\in\mathcal{N}_{t}$ and hence, $q_{t}$ is well-defined. Let $\ell_{t}:=\lceil\log q_{t}\rceil$ . Then, the algorithm samples a value $R_{t}$ from $[\ell_{t}-3\lceil\log r\rceil,\ell_{t}+3\lceil\log r\rceil]$ uniformly at random. Finally, the algorithm sets $C(e_{t})$ to be an integer picked uniformly at random from $[\lfloor 2^{R_{t}}/(60\cdot\log^{2}r)\rfloor]$ . We give a pseudocode of the algorithm in Algorithm 1.

Algorithm 1 Randomized Online Algorithm for Disj-Polymatroid-Bases.

3.2 Ordered Min-sized Quotients Property

In this section, we show that there can be at most $r$ distinct arrival times $t$ with the same value of $q_{t}$ .

Lemma 7.

Let $f:2^{{\mathcal{N}}}\rightarrow\mathbb{Z}_{\geq 0}$ be a polymatroid over the ground set ${\mathcal{N}}$ with $f(e)>0$ for every $e\in\mathcal{N}$ and $f(\emptyset)=0$ . Let $e_{1},e_{2},\ldots,e_{n}$ be an ordering of the ground set ${\mathcal{N}}$ . For every $t\in[n]$ , we define

q_{t}:=\min\left\{|Q|:e_{t}\in Q\subseteq{\mathcal{N}}_{t}\text{ and $Q$ is a % quotient of $f_{|{\mathcal{N}}_{t}}$}\right\}.

Then, for every $j\in\mathbb{Z}_{+}$ ,

|\left\{t\in[n]:q_{t}=j\right\}|\leq r.

Proof.

We note that $q_{t}$ is well-defined: empty set is closed since $f(e)>0$ for every $e\in{\mathcal{N}}$ and hence, ${\mathcal{N}}_{t}$ is a quotient of $f_{|{\mathcal{N}}_{t}}$ containing $e_{t}$ for every $t\in[n]$ . Let $j\in\mathbb{Z}_{+}$ . Let $t_{1}<t_{2}<\ldots<t_{\ell}$ be the timesteps $t$ with $q_{t}=j$ . It suffices to show that $\ell\leq r$ . For every $i\in[\ell]$ , let $Q_{t_{i}}$ be a minimum sized quotient of $f_{|\mathcal{N}_{t_{i}}}$ containing element $e_{t_{i}}$ . We note that $|Q_{t_{i}}|=q_{t_{i}}=j$ for every $i\in[\ell]$ . We define $S:=\bigcup_{i=1}^{\ell}\left(Q_{t_{i}}\setminus e_{t_{i}}\right)$ .

We first show that $e_{t_{i}}\not\in S$ for every $i\in[\ell]$ . Suppose there exists an element $e_{t_{i_{1}}}\in S$ . Then, there exists an index $i_{2}\in[\ell]$ such that $e_{t_{i_{1}}}\in Q_{t_{i_{2}}}\setminus e_{t_{i_{2}}}$ . Hence, $e_{t_{i_{1}}}\in Q_{t_{i_{2}}}\setminus e_{t_{i_{2}}}\subseteq\mathcal{N}_{t_{% i_{2}}}$ , which implies that $i_{1}\leq i_{2}$ . Since $e_{t_{i_{1}}}\not\in Q_{t_{i_{1}}}\setminus e_{t_{i_{1}}}$ , we have $i_{1}\neq i_{2}$ , which shows that $i_{1}<i_{2}$ . By Lemma 4, $Q_{t_{i_{2}}}\cap\mathcal{N}_{t_{i_{1}}}$ is a quotient of $f_{|\mathcal{N}_{t_{i_{1}}}}$ . We note that $|Q_{t_{i_{2}}}\cap\mathcal{N}_{t_{i_{1}}}|<|Q_{t_{i_{2}}}|=j$ since $e_{t_{i_{2}}}\in Q_{t_{i_{2}}}$ and $e_{t_{i_{2}}}\not\in Q_{t_{i_{2}}}\cap\mathcal{N}_{t_{i_{1}}}$ . Consequently, $Q_{t_{i_{2}}}\cap\mathcal{N}_{t_{i_{1}}}$ contradicts the fact that the smallest quotient of $f_{|\mathcal{N}_{t_{i_{1}}}}$ containing element $e_{t_{i_{1}}}$ has size exactly $j$ . Hence, $e_{t_{i}}\not\in S$ for every $i\in[\ell]$ .

We now show that $f(\mathcal{N}_{t_{i}}\setminus S)<f(\mathcal{N}_{t_{i+1}}\setminus S)$ for every $i\in[\ell-1]$ . Let $i\in[\ell-1]$ . Since $Q_{t_{i+1}}$ is a quotient of $\mathcal{N}_{t_{i+1}}$ containing element $e_{t_{i+1}}$ , we have $f_{\mathcal{N}_{t_{i+1}}\setminus Q_{t_{i+1}}}(e_{t_{i+1}})>0$ . Since function $f$ is submodular, we have

f(\mathcal{N}_{t_{i+1}}\setminus S)-f(\mathcal{N}_{t_{i+1}-1}\setminus S)=f_{% \mathcal{N}_{t_{i+1}-1}\setminus S}(e_{t_{i+1}})\geq f_{\mathcal{N}_{t_{i+1}}% \setminus Q_{t_{i+1}}}(e_{t_{i+1}})>0.

Hence,

f(\mathcal{N}_{t_{i}}\setminus S)\leq f(\mathcal{N}_{t_{i+1}-1}\setminus S)<f(% \mathcal{N}_{t_{i+1}}\setminus S),

where the first inequality is by monotonicity of the function $f$ . Thus, we have $f(\mathcal{N}_{t_{i}}\setminus S)<f(\mathcal{N}_{t_{i+1}}\setminus S)$ for every $i\in[\ell-1]$ .

This implies that $\{f(\mathcal{N}_{t_{i}}\setminus S)\}_{i=1}^{\ell}$ is a strictly increasing integer sequence. We note that $f(\mathcal{N}_{t_{\ell}}\setminus S)\leq r$ . Also, since $f$ is a monotone function, we have $f(\mathcal{N}_{t_{1}}\setminus S)\geq f(e_{t_{1}})>0$ . Hence, $\ell\leq r$ . $\hfill\blacktriangleleft$

3.3 Structural Property

For each $t\in[n]$ , we define the element $e_{t}$ to be good if $\frac{k^{*}}{2r}<q_{t}<2rk^{*}$ and bad otherwise. Let $\mathcal{N}_{\mathsf{good}}$ be the set of good elements. The following is the main result of this section. It shows that bases of $f_{|{\mathcal{N}}_{\mathsf{good}}}$ are also bases of $f$ and moreover, the quantity $k^{*}(f_{|{\mathcal{N}}_{\mathsf{good}}})$ is at least a constant fraction of $k^{*}(f)$ .

Lemma 8.

We have that

1.

$f({\mathcal{N}}_{\mathsf{good}})=f({\mathcal{N}})$ and
2.

$k^{*}(f_{|{\mathcal{N}}_{\mathsf{good}}})\geq\frac{1}{2}k^{*}(f)$ .

We prove Lemma 8 in a series of steps. We note that an element $e_{t}$ could be bad because of two reasons: either $q_{t}$ is too large or it is too small. We first show that the only reason for certain elements being bad is that their $q_{t}$ is too small.

Lemma 9.

Let $A\subseteq\mathcal{N}$ be a closed set of $f$ . Let $T\geq 1$ be the smallest integer such that

\sum_{e\in\mathcal{N}_{T}\setminus A}\left(f(A+e)-f(A)\right)\geq k^{*}\cdot% \left(f(\mathcal{N})-f(A)\right).

(4)

Then, for every element $e_{t}\in\mathcal{N}_{T}\setminus A$ with $t\in[T]$ , we have that $q_{t}<2rk^{*}$ .

Proof.

We recall that $k^{*}=k^{*}(f)$ . By definition of $k^{*}$ , we have

\sum_{e\in\mathcal{N}\setminus A}\left(f(A+e)-f(A)\right)\geq k^{*}\cdot\left(% f(\mathcal{N})-f(A)\right).

Since $T$ is the smallest integer satisfying inequality (4), we have

\sum_{e\in\mathcal{N}_{T-1}\setminus A}\left(f(A+e)-f(A)\right)<k^{*}\cdot% \left(f(\mathcal{N})-f(A)\right).

(5)

Hence,

$\displaystyle\sum_{e\in\mathcal{N}_{T}\setminus A}\left(f(A+e)-f(A)\right)$	$\displaystyle=\left(\sum_{e\in\mathcal{N}_{T-1}\setminus A}\left(f(A+e)-f(A)% \right)\right)+\left(f(A+e_{T})-f(A)\right)$
	$\displaystyle<k^{*}\cdot\left(f(\mathcal{N})-f(A)\right)+\left(f(A+e_{T})-f(A)% \right)\ \ \text{(by inequality\leavevmode\nobreak\ (\ref{inequality:new-T}))}$
	$\displaystyle\leq k^{*}\cdot\left(f(\mathcal{N})-f(A)\right)+\left(f(\mathcal{% N})-f(A)\right)\ \ \text{(since $f(A+e_{T})\leq f(\mathcal{N})$)}$
	$\displaystyle=(k^{*}+1)\cdot\left(f(\mathcal{N})-f(A)\right).$	(6)

Since $A$ is a closed set, we have $f(A+e)-f(A)\geq 1$ for every element $e\in\mathcal{N}_{T}\setminus A$ . Thus, using inequality (3.3), we have

|\mathcal{N}_{T}\setminus A|<\sum_{e\in\mathcal{N}_{T}\setminus A}\left(f(A+e)% -f(A)\right)\leq(k^{*}+1)\cdot(f(\mathcal{N})-f(A))\leq(k^{*}+1)r<2rk^{*}.

(7)

Since $A$ is a closed set, $\mathcal{N}\setminus A$ is a quotient of $f$ . By Lemma 4, for every $t\in[n]$ , we know that $\mathcal{N}_{t}\setminus A$ is a quotient of $f_{|\mathcal{N}_{t}}$ . Hence, for every element $e_{t}\in\mathcal{N}_{T}\setminus A$ with $t\in[T]$ , we have that $q_{t}\leq|\mathcal{N}_{t}\setminus A|\leq|\mathcal{N}_{T}\setminus A|<2rk^{*}$ , where the last inequality is by inequality (7). $\hfill\blacktriangleleft$

Next, we show that dropping all bad elements will not decrease the value of $k^{*}$ by more than a constant factor for all sets. We first show this for closed sets (Lemma 10) and derive it for arbitrary sets as a corollary (Corollary 11).

Lemma 10.

For every closed set $A\subseteq\mathcal{N}$ ,

\sum_{e\in\mathcal{N}_{\mathsf{good}}\setminus A}\left(f(A+e)-f(A)\right)\geq% \frac{k^{*}}{2}\cdot\left(f(\mathcal{N})-f(A)\right).

Proof.

Let $A\subseteq\mathcal{N}$ be a closed set. Let $T\geq 1$ be the smallest integer such that inequality (4) holds. Lemma 9 implies that for every $t\in[T]$ , element $e_{t}\in\mathcal{N}_{T}\setminus A$ is bad if and only if $q_{t}\leq\frac{k^{*}}{2r}$ . Hence, we have

$\displaystyle\|\mathcal{N}_{T}\setminus(A\cup\mathcal{N}_{\mathsf{good}})\|$	$\displaystyle=\|\{t\in[T]:e_{t}\in\mathcal{N}_{T}\setminus(A\cup\mathcal{N}_{% \mathsf{good}})\}\|=\left\|\left\{t\in[T]:e_{t}\in\mathcal{N}_{T}\setminus A\ \&% \ q_{t}\leq\frac{k^{*}}{2r}\right\}\right\|$
	$\displaystyle\leq\left\|\left\{t\in[T]:q_{t}\leq\frac{k^{}}{2r}\right\}\right\|% =\sum_{j=1}^{\lfloor\frac{k^{}}{2r}\rfloor}\left\|\{t\in[T]:q_{t}=j\}\right\|$
	$\displaystyle\leq\left(\frac{k^{*}}{2r}\right)r\ \ \text{(by Lemma\leavevmode% \nobreak\ \ref{lemma:counting-quotient})}$
	$\displaystyle=\frac{k^{*}}{2}.$	(8)

Thus,

	$\displaystyle\sum_{e\in\mathcal{N}_{\mathsf{good}}\setminus A}\left(f(A+e)-f(A% )\right)$
	$\displaystyle\quad\quad\quad\geq\sum_{e\in(\mathcal{N}_{T}\cap\mathcal{N}_{% \mathsf{good}})\setminus A}\left(f(A+e)-f(A)\right)\ \ \text{(since $f(A+e)% \geq f(A)$ for every $e\in\mathcal{N}$)}$
	$\displaystyle\quad\quad\quad=\sum_{e\in\mathcal{N}_{T}\setminus A}\left(f(A+e)% -f(A)\right)-\sum_{e\in\mathcal{N}_{T}\setminus(A\cup\mathcal{N}_{\mathsf{good% }})}\left(f(A+e)-f(A)\right)$
	$\displaystyle\quad\quad\quad\geq k^{}\cdot\left(f(\mathcal{N})-f(A)\right)-% \sum_{e\in\mathcal{N}_{T}\setminus(A\cup\mathcal{N}_{\mathsf{good}})}\left(f(A% +e)-f(A)\right)\ \ \text{(by inequality\leavevmode\nobreak\ (\ref{inequality-% for-bad:k^}))}$
	$\displaystyle\quad\quad\quad\geq k^{*}\cdot\left(f(\mathcal{N})-f(A)\right)-% \sum_{e\in\mathcal{N}_{T}\setminus(A\cup\mathcal{N}_{\mathsf{good}})}\left(f(% \mathcal{N})-f(A)\right)\ \ \text{(by monotonicity of $f$)}$
	$\displaystyle\quad\quad\quad\geq k^{}\cdot\left(f(\mathcal{N})-f(A)\right)-% \frac{k^{}}{2}\cdot\left(f(\mathcal{N})-f(A)\right)\ \ \text{(by inequality% \leavevmode\nobreak\ (\ref{inequality:good-elements}))}$
	$\displaystyle\quad\quad\quad=\frac{k^{*}}{2}\cdot\left(f(\mathcal{N})-f(A)% \right).$

$\hfill\blacktriangleleft$

Corollary 11.

For every set $A\subseteq\mathcal{N}$ ,

\sum_{e\in\mathcal{N}_{\mathsf{good}}\setminus A}\left(f(A+e)-f(A)\right)\geq% \frac{k^{*}}{2}\cdot\left(f(\mathcal{N})-f(A)\right).

Proof.

We have

	$\displaystyle\sum_{e\in\mathcal{N}_{\mathsf{good}}\setminus A}(f(A+e)-f(A))$	$\displaystyle\geq\sum_{e\in\mathcal{N}_{\mathsf{good}}\setminus\text{span}(A)}% (f(A+e)-f(A))\ \ \text{(since $A\subseteq\text{span}(A)$)}$
		$\displaystyle\geq\sum_{e\in\mathcal{N}_{\mathsf{good}}\setminus\text{span}(A)}% (f(\text{span}(A)+e)-f(\text{span}(A))$
		(since $f_{A}(e)\geq f_{\text{span}(A)}(e)$ by submodularity of $f$ )
		$\displaystyle\geq\frac{k^{*}}{2}\cdot(f(\mathcal{N})-f(\text{span}(A)))\ \ % \text{\footnotesize(by applying Lemma\leavevmode\nobreak\ \ref{lemma:new-ratio% -closed} for $\text{span}(A)$)}$
		$\displaystyle=\frac{k^{*}}{2}\cdot(f(\mathcal{N})-f(A)).\ \ \text{% \footnotesize(since $f(A)=f(\text{span}(A))$)}\$

$\hfill\blacktriangleleft$

We now prove Lemma 8.

Proof of Lemma 8.

We recall that $k^{*}=k^{*}(f)>0$ by assumption. By applying Corollary 11 for $A=\mathcal{N}_{\mathsf{good}}$ , we conclude that $f(\mathcal{N})=f(\mathcal{N}_{\mathsf{good}})$ . Hence,

k^{*}(f_{|{\mathcal{N}}{\mathsf{good}}})=\min_{A\subseteq\mathcal{N}_{\mathsf{% good}}:f(A)<f(\mathcal{N}_{\mathsf{good}})}\frac{\sum_{e\in\mathcal{N}_{% \mathsf{good}}}f_{A}(e)}{f(\mathcal{N}_{\mathsf{good}})-f(A)}=\min_{A\subseteq% \mathcal{N}_{\mathsf{good}}:f(A)<f(\mathcal{N}_{\mathsf{good}})}\frac{\sum_{e% \in\mathcal{N}_{\mathsf{good}}\setminus A}f_{A}(e)}{f(\mathcal{N})-f(A)},

where the last equality holds since $f_{A}(e)=0$ for every $e\in A$ and $f({\mathcal{N}}_{\mathsf{good}})=f({\mathcal{N}})$ . By Corollary 11, for every set $A\subseteq\mathcal{N}$ with $f(A)<f({\mathcal{N}}_{\mathsf{good}})$ , we have

\frac{\sum_{e\in\mathcal{N}_{\mathsf{good}}\setminus A}f_{A}(e)}{f(\mathcal{N}% )-f(A)}\geq\frac{k^{*}}{2}.

Hence, $k^{*}(f_{|{\mathcal{N}}{\mathsf{good}}})\geq\frac{1}{2}k^{*}$ . $\hfill\blacktriangleleft$

3.4 Competitive Ratio Analysis

Now, we analyze the competitive ratio of Algorithm 1. Let $h:=\lfloor\log k^{*}\rfloor$ . We note that $\frac{k^{*}}{2}<2^{h}\leq k^{*}$ . We now prove that every color $c\in[\lfloor 2^{h}/(60\cdot\log^{2}r)\rfloor]$ is a base color with constant probability in Algorithm 1.

Lemma 12.

Let $c\in[\lfloor 2^{h}/(60\cdot\log^{2}r)\rfloor]$ . Then, $\mathbf{Pr}_{\texttt{Alg${}_{1}$}}[c\text{ is a base color}]\geq\frac{1}{2}$ .

Proof.

Let $k^{*}_{\mathsf{good}}:=k^{*}(f_{|{\mathcal{N}}_{\mathsf{good}}})$ . We recall that $k^{*}=k^{*}(f)$ . By Lemma 8, we have that $f({\mathcal{N}}_{\mathsf{good}})=f({\mathcal{N}})$ and hence, bases of $f_{|{\mathcal{N}}_{\mathsf{good}}}$ correspond to bases of $f$ . By Lemma 8, we also have that $k^{*}_{\mathsf{good}}\geq\frac{k^{*}}{2}\geq 2^{h-1}$ . Let $e_{t}\in\mathcal{N}_{\mathsf{good}}$ . We have $\frac{k^{*}}{2r}<q_{t}<2rk^{*}$ and hence, $\lceil\log q_{t}\rceil-3\lceil\log r\rceil\leq h\leq\lceil\log q_{t}\rceil+3% \lceil\log r\rceil$ . Therefore,

\mathbf{Pr}[R_{t}=h]=\frac{1}{6\lceil\log r\rceil+1}>\frac{1}{15\log r}.

(9)

Hence, for every element $e_{t}\in\mathcal{N}_{\mathsf{good}}$ , the probability that $e_{t}$ is colored with $c$ is

	$\displaystyle\mathbf{Pr}[C(e_{t})=c]$	$\displaystyle\geq\mathbf{Pr}[R_{t}=h]\cdot\mathbf{Pr}[C(e_{t})=c\|r_{t}=h]$
		$\displaystyle=\mathbf{Pr}[R_{t}=h]\cdot\frac{1}{\lfloor 2^{h}/(60\cdot\log^{2}% r)\rfloor}$
		$\displaystyle>\frac{1}{15\log r}\cdot\frac{60\cdot\log^{2}r}{2^{h}}\ \ \text{(% by inequality\leavevmode\nobreak\ (\ref{inequality:probability-analysis}))}$
		$\displaystyle\geq\frac{1}{15\log r}\cdot\frac{60\cdot\log^{2}r}{2k_{\mathsf{% good}}^{}}=\frac{2\log r}{k^{}_{\mathsf{good}}}.$

We recall that $k^{*}_{\mathsf{good}}=k^{*}(f_{|{\mathcal{N}}_{\mathsf{good}}})$ . By applying Lemma 6 for the polymatroid $f_{|\mathcal{N}_{\mathsf{good}}}$ , we conclude that the elements in $\mathcal{N}_{\mathsf{good}}$ with color $c$ form a base of $f_{|\mathcal{N}_{\mathsf{good}}}$ with probability at least $\frac{1}{2}$ . We recall that bases of $f_{|{\mathcal{N}}_{\mathsf{good}}}$ are also bases of $f$ . Hence, $c$ is a base color with probability at least $\frac{1}{2}$ . $\hfill\blacktriangleleft$

Lemma 12 implies a lower bound on the expected number of base colors obtained by Algorithm 1.

Corollary 13.

The expected number of base colors obtained by Algorithm 1 is at least

\mathbb{E}[\texttt{Alg${}_{1}$}(f)]\geq\frac{1}{2}\cdot\lfloor 2^{h}/(60\cdot% \log^{2}r)\rfloor.

Proof.

By Lemma 12, we have that

\mathbb{E}[\texttt{Alg${}_{1}$}(f)]=\sum_{c\in[\lfloor 2^{h}/(60\cdot\log^{2}r% )\rfloor]}\mathbf{Pr}_{\texttt{Alg${}_{1}$}}[c\text{ is a base color}]\geq% \frac{1}{2}\cdot\lfloor 2^{h}/(60\cdot\log^{2}r)\rfloor.\

$\hfill\blacktriangleleft$

3.5 Combined Algorithm

We recall that our analysis of Algorithm 1 assumed that $r\geq 2$ and $k^{*}\geq 120\log^{2}r$ . We now combine Algorithm 1 with other algorithms to address all ranges of $r$ and $k^{*}$ .

Consider the online algorithm Alg ${}_{1}^{*}$ that runs Algorithm 1 with probability $\frac{1}{3}$ , assigns $C(e_{t})=1$ for every element $e_{t}$ with probability $\frac{1}{3}$ , and assigns $C(e_{t})=t$ for every element $e_{t}$ with probability $\frac{1}{3}$ . We show that the resulting online algorithm Alg ${}_{1}^{*}$ has competitive ratio $O(\log^{2}r)$ .

Theorem 14.

Algorithm Alg ${}_{1}^{*}$ has competitive ratio $O(\log^{2}r)$ .

Proof.

Suppose $r=1$ . Then, each singleton forms a base, which implies that $\texttt{opt}(f)=n$ . We recall that the algorithm assigns $C(e_{t})=t$ for every element $e_{t}$ with probability $\frac{1}{3}$ . This implies that

\displaystyle\mathbb{E}[\texttt{Alg${}_{1}^{*}$}(f)]\geq\frac{1}{3}\cdot% \texttt{opt}(f).

Suppose $r\geq 2$ and $k^{*}<120\log^{2}r$ . Then, the optimum is also smaller than $120\log^{2}r$ by Theorem 5. We recall that the algorithm assigns $C(e_{t})=1$ for every element $e_{t}$ with probability $\frac{1}{3}$ . This implies that

\displaystyle\mathbb{E}[\texttt{Alg${}_{1}^{*}$}(f)]\geq\frac{1}{3}>\frac{1}{3% 60\log^{2}r}\cdot\texttt{opt}(f).

Now, we may assume that $k^{*}\geq 120\log^{2}r$ and $r\geq 2$ . We recall that the algorithm Alg ${}_{1}^{*}$ runs Algorithm 1 with probability $\frac{1}{3}$ . We have

2^{h}/(60\cdot\log^{2}r)>\frac{1}{60}\cdot\frac{k^{*}}{2\log^{2}r}\geq 1,

(10)

which implies that

\lfloor 2^{h}/(60\cdot\log^{2}r)\rfloor\geq\frac{1}{2}\cdot 2^{h}/(60\cdot\log% ^{2}r).

(11)

Hence, we have

	$\displaystyle\mathbb{E}[\texttt{Alg${}_{1}^{*}$}(f)]$	$\displaystyle\geq\frac{1}{3}\cdot\mathbb{E}[\texttt{Alg${}_{1}$}(f)]$
		$\displaystyle\geq\frac{1}{6}\cdot\lfloor 2^{h}/(60\cdot\log^{2}r)\rfloor\ \ % \text{(by Corollary\leavevmode\nobreak\ \ref{corollary:number-proper-colors})}$
		$\displaystyle\geq\frac{1}{12}\cdot 2^{h}/(60\cdot\log^{2}r)\ \ \text{(by % inequality\leavevmode\nobreak\ (\ref{inequality:trunc-integer}))}$
		$\displaystyle\geq\frac{1}{1440\cdot\log^{2}r}\cdot k^{*}$
		$\displaystyle\geq\frac{1}{1440\cdot\log^{2}r}\cdot\texttt{opt}(f).\ \ \text{(% by Theorem\leavevmode\nobreak\ \ref{thm:CCV-k^*})}$

$\hfill\blacktriangleleft$

4 Approximation of $q_{t}$ in Polynomial Time

In Section 3, we presented a randomized online algorithm with competitive ratio $O(\log^{2}r)$ . The algorithm takes exponential time, since the parameter $q_{t}=\min\{|Q|:e_{t}\in Q\subseteq\mathcal{N}_{t}\text{ and $Q$ is a quotient% of $f_{|\mathcal{N}_{t}}$}\}$ is NP-hard to compute. In this section, we show how to get an approximation of $q_{t}$ in polynomial time via strength decomposition of the function $f$ .

Strength Decomposition.

We first introduce the definition of strength decomposition. Let $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ be a polymatroid over the ground set $\mathcal{N}$ . For a subset $T$ of $S$ , the strength-ratio of $T$ in $S$ , denoted $\varphi(T|S)$ , is the value $\varphi(T|S):=\frac{|S|-|T|}{f(S)-f(T)}$ , with the convention that $x/0=+\infty$ for every $x\geq 0$ .

Definition 15.

[12] Let $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ be a polymatroid over the ground set $\mathcal{N}$ . A strength decomposition of $\mathcal{N}$ with respect to $f$ is a sequence of sets $S_{0}\supseteq S_{1}\supseteq\ldots\supseteq S_{w}$ such that: (i) $S_{0}=\mathcal{N}$ , (ii) $S_{w}=\emptyset$ and $S_{i}\neq\emptyset$ for every $i\in[0,w-1]$ , (iii) for every $i\in[w]$ , $S_{i}=\mathop{argmin}\limits_{S\subseteq S_{i-1}}\ \varphi(S|S_{i-1})$ , and (iv) the strength ratios $\varphi(S_{i}|S_{i-1})$ are nondecreasing in $i$ .

For every polymatroid $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ over a ground set ${\mathcal{N}}$ , there exists a strength decomposition of ${\mathcal{N}}$ with respect to $f$ and it can be computed in polynomial time via reduction to submodular minimization [9, 10, 8] (also see [12]). We further show that all sets in a strength decomposition are closed.

Lemma 16.

Let $f:2^{\mathcal{N}}\rightarrow\mathbb{Z}_{\geq 0}$ be a polymatroid over the ground set $\mathcal{N}$ . Let ${\mathcal{N}}=S_{0}\supseteq S_{1}\supseteq\ldots\supseteq S_{w}=\emptyset$ be a strength decomposition with respect to $f$ . Then, $S_{i}$ is a closed set for every $i\in[0,w]$ .

Approximating $q_{t}$ in Polynomial Time.

Now, we show how to approximate $q_{t}$ in polynomial time. For every timestep $t\in[n]$ , let ${\mathcal{N}}_{t}=S_{0}\supseteq S_{1}\supseteq\ldots\supseteq S_{w}=\emptyset$ be a strength decomposition with respect to $f_{|\mathcal{N}_{t}}$ . Let $i\in[0,w]$ be the index such that $e_{t}\in S_{i-1}\setminus S_{i}$ . We define $\eta_{t}:=\frac{|\mathcal{N}_{t}\setminus S_{i}|}{f(\mathcal{N}_{t})-f(S_{i})}$ . We prove that the parameter $\eta_{t}$ is an $r$ -approximation of $q_{t}$ .

Lemma 17.

For every $t\in[n]$ , $\frac{q_{t}}{r}\leq\eta_{t}\leq q_{t}$ .

Replacing the estimate $q_{t}$ in Algorithm 1 by $\eta_{t}$ gives a randomized online algorithm in polynomial time with the same competitive ratio, which completes the proof of Theorem 1.

5 Simpler Algorithm for Online Disj-Conn-Spanning-Subhypergraphs

In this section, we consider Disj-Conn-Spanning-Subhypergraphs. The input here is a connected hypergraph $G=(V,E)$ where each hyperedge $e\in E$ is a non-empty subset of $V$ . We use $n:=|V|$ and $m:=|E|$ to denote the number of vertices and hyperedges in the hypergraph respectively. We note that $E$ is a multi-set, i.e., it can contain multiple copies of the same hyperedge. We recall that the hypergraph $G=(V,E)$ can equivalently be represented as a bipartite graph $G^{\prime}=(V\cup E,E^{\prime})$ , where we have a node for each vertex $u\in V$ and each hyperedge $e\in E$ and an edge between nodes $u\in V$ and $e\in E$ if the hyperedge $e$ contains the vertex $u$ . A hypergraph is connected if its bipartite representation is connected. A subhypergraph of $G$ is a subset of hyperedges $F\subseteq E$ and it is said to be spanning if $\cup_{e\in F}e=V$ and connected if $(V,F)$ is connected. The goal is to find a maximum number of disjoint connected spanning subhypergraphs.

In the online model for Disj-Conn-Spanning-Subhypergraphs, the set $V$ of nodes is known in advance while the hyperedges $E$ arrive in an online fashion. For a color assignment $C:E\rightarrow\mathbb{Z}_{+}$ , we say that a color $c\in\mathbb{Z}_{+}$ is a connected spanning color if the set of hyperedges with color $c$ is spanning and connected. An online algorithm has to color each hyperedge immediately upon arrival irrevocably in order to maximize the number of connected spanning colors. Theorem 1 implies a randomized online algorithm for this problem with competitive ratio $O(\log^{2}n)$ that runs in polynomial time. We show that we can achieve the same competitive ratio via a much simpler estimator.

For every integer $t\in[m]$ , let $e_{t}$ be the hyperedge arriving at time $t$ . Define $E_{t}:=\{e_{1},\ldots,e_{t}\}$ as the set of hyperedges that have arrived until time $t$ . For a subset $S\subseteq V$ of nodes, let $E_{t}(S):=\{e\in E_{t}:S\subseteq e\}$ be the set of hyperedges containing all vertices in $S$ that have arrived until time $t$ . We define

\eta_{t}:=\min_{\{u,v\}\in e_{t}:\ u\neq v}|E_{t}(\{u,v\})|.

Equivalently, $\eta_{t}$ is the min over all pairs of vertices in the current hyperedge of the number of hyperedges containing the pair in the current hypergraph. We prove that replacing the estimate $q_{t}$ in Algorithm 1 by $\eta_{t}$ gives a randomized online algorithm with the same competitive ratio. We note that $|E_{t}(\{u,v\})|$ for every $u,v\in V$ can be maintained in $O(|e_{t}|^{2})$ time in the $t$ -th timestep, which implies that the algorithm takes $O(|e_{t}|^{2})$ time in the $t$ -th timestep.

6 Conclusion

Packing bases of a polymatroid generalizes numerous set packing problems including disjoint bases of a matroid, disjoint spanning trees of a graph, disjoint set covers of a set system, and disjoint connected spanning subhypergraphs of a hypergraph. In this work, we introduced an online model for packing bases of a polymatroid and gave an algorithm that achieves a polylogarithmic competitive ratio. Our algorithm leads to a polylogarithmic competitive ratio for all these packing problems in a unified fashion. Our algorithm is based on novel properties of the notion of quotients of polymatroids. For the special cases of disjoint spanning trees of a graph and disjoint connected spanning subhypergraphs of a hypergraph, we gave a simpler and more elegant online algorithm that is also easy to implement while achieving the same polylogarithmic competitive ratio.

Our work leads to several interesting open questions. We mention three prominent ones: Firstly, we recall that Disj-Spanning-Trees (and more generally, Disj-Matroid-Bases) in the offline setting is polynomial-time solvable via matroidal techniques. Is it possible to design an online algorithm for Disj-Spanning-Trees (and more generally, for Disj-Matroid-Bases) with constant competitive ratio? Secondly, it is known that there is no randomized algorithm with expected impure competitive ratio $o(\log{n}/\log\log{n})$ for Disj-Set-Cover, where $n$ is the size of the ground set. Can we show that there is no randomized algorithm with expected impure competitive ratio $o(\log{f({\mathcal{N}})})$ or pure competitive ratio $o(\log^{2}{f({\mathcal{N}})})$ for Disj-Polymatroid-Bases? Thirdly, we recall that our online model for Disj-Polymatroid-Bases assumes knowledge of $f({\mathcal{N}})$ . Is it possible to achieve polylogarithmic competitive ratio without knowledge of $f({\mathcal{N}})$ ? This seems to be open even in the special case of coverage functions (i.e., for online Disj-Set-Cover) [6].

References

[1] M. Bienkowski, J. Byrka, and $\mathsf{L}$ . Jeż. Online Disjoint Set Covers: Randomization Is Not Necessary. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, pages 18:1–18:16, 2025.
[2] G. Călinescu, C. Chekuri, and J. Vondrák. Disjoint bases in a polymatroid. Random Struct. Algorithms, 35(4):418–430, 2009. doi:10.1002/RSA.20274.
[3] K. Chandrasekaran, C. Chekuri, and W. Zhu. Online disjoint spanning trees and polymatroid bases. arXiv preprint arXiv:2503.19999, 2025.
[4] J. Cheriyan and M. R. Salavatipour. Packing element-disjoint steiner trees. ACM Trans. Algorithms, 3(4):47, 2007. doi:10.1145/1290672.1290684.
[5] J. Edmonds. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards B, 69:73–77, 1965.
[6] Y. Emek, A. Goldbraikh, and E. Kantor. Online Disjoint Set Cover Without Prior Knowledge. In 27th Annual European Symposium on Algorithms (ESA), pages 44:1–44:16, 2019.
[7] U. Feige, M. M. Halldórsson, G. Kortsarz, and A. Srinivasan. Approximating the domatic number. SIAM Journal on Computing, 32(1):172–195, 2002. doi:10.1137/S0097539700380754.
[8] S. Fujishige. Theory of principal partitions revisited. Research Trends in Combinatorial Optimization, pages 127–162, 2009.
[9] H. Narayanan. The principal lattice of partitions of a submodular function. Linear Algebra and its Applications, 144:179–216, 1991.
[10] H. Narayanan. Submodular functions and electrical networks, volume 54. Elsevier, 1997.
[11] A. Pananjady, V. K. Bagaria, and R. Vaze. The online disjoint set cover problem and its applications. In 2015 IEEE Conference on Computer Communications (INFOCOM), pages 1221–1229, 2015.
[12] K. Quanrud. Quotient sparsification for submodular functions. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5209–5248, 2024.
[13] A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003.

Appendix A Quotients for some concrete polymatroids

For a polymatroid $h:2^{\mathcal{V}}\rightarrow\mathbb{Z}_{\geq 0}$ , we recall that a set $Q\subseteq\mathcal{V}$ is a quotient of $h$ if $h(e+(\mathcal{V}\setminus Q))>h(\mathcal{V}\setminus Q)$ $\forall e\in Q$ , i.e., if each element $e\in Q$ has strictly positive marginal with respect to $\mathcal{V}\setminus Q$ . Since the definition of quotients might seem contrived, we interpret it for some concrete polymatroids:

1.

Let $G=(V,E)$ be a connected hypergraph (graph respectively). Consider the polymatroid $h:2^{E}\rightarrow\mathbb{Z}_{\geq 0}$ that arises in Disj-Conn-Spanning-Subhypergraphs (Disj-Spanning-Trees respectively) with $G$ being the input instance. Quotients of $h$ correspond to union of cut-set of disjoint subsets of vertices, i.e., each quotient $Q\subseteq E$ of $h$ is of the form $Q=\cup_{S\in\mathcal{C}}\delta(S)$ , where the family $\mathcal{C}\subseteq 2^{V}\setminus\{\emptyset,V\}$ is a disjoint family of subsets of vertices. In particular, the minimum size of a non-empty quotient is equal to the global min-cut value of $G$ .
2.

Let $G=(V,E)$ be a hypergraph. Consider the polymatroid $h:2^{E}\rightarrow\mathbb{Z}_{\geq 0}$ that arises in Disj-Set-Cover with $G$ being the input instance, i.e., $h$ is the coverage function of $G$ . Quotients of $h$ correspond to union of vertex-isolating cuts of $G$ , i.e., each quotient $Q\subseteq E$ of $h$ is of the form $Q=\cup_{u\in S}\delta(u)$ where $S\subseteq V$ . In particular, the minimum size of a non-empty quotient is equal to the min-degree of $G$ .

Appendix B Min-size of a non-empty Quotient and $k^{*}$

Let $q^{*}$ be the minimum size of non-empty quotients of $f$ , i.e.,

q^{*}:=\min\{|Q|:\emptyset\neq Q\subseteq\mathcal{N}\text{ is a quotient of $f% $}\}.

We recall that

k^{*}=k^{*}(f)=\min_{A\subseteq\mathcal{N}:f(A)<f(\mathcal{N})}\left\lfloor% \frac{\sum_{e\in\mathcal{N}}f_{A}(e)}{f(\mathcal{N})-f(A)}\right\rfloor.

The following lemma shows that $q^{*}$ is an $r$ -approximation of $k^{*}$ .

Lemma 18.

$\frac{q^{*}}{r}-1<k^{*}\leq q^{*}$ .

Proof.

We first show the lower bound on $k^{*}$ . Consider a closed set $A\subseteq\mathcal{N}$ with $f(A)<f(\mathcal{N})$ and $k^{*}=\left\lfloor\frac{\sum_{e\in\mathcal{N}}f_{A}(e)}{f(\mathcal{N})-f(A)}\right\rfloor$ . Since $A$ is closed, we have that $f_{A}(e)\geq 1$ for every $e\in\mathcal{N}\setminus A$ and $\mathcal{N}\setminus A$ is a quotient of $f$ . Therefore, we have

	$\displaystyle k^{*}=\left\lfloor\frac{\sum_{e\in\mathcal{N}}f_{A}(e)}{f(% \mathcal{N})-f(A)}\right\rfloor$	$\displaystyle>\frac{\sum_{e\in\mathcal{N}}f_{A}(e)}{f(\mathcal{N})-f(A)}-1\ \ % \text{(since $\lfloor x\rfloor>x-1$)}$
		$\displaystyle\geq\frac{\sum_{e\in\mathcal{N}}f_{A}(e)}{r}-1\ \ \text{(since $f% (\mathcal{N})-f(A)\leq f(\mathcal{N})\leq r$)}$
		$\displaystyle\geq\frac{\|\mathcal{N}\setminus A\|}{r}-1\ \ \text{(since $f_{A}(e% )\geq 1$ for every $e\in\mathcal{N}\setminus A$)}$
		$\displaystyle\geq\frac{q^{*}}{r}-1.\ \ \text{(since $\mathcal{N}\setminus A$ % is a quotient of $f$)}$

We now show the upper bound on $k^{*}$ . Consider a minimum sized non-empty quotient $Q$ . Let $A:=\mathcal{N}\setminus Q$ . Since $A$ is a closed set and $A\neq\mathcal{N}$ , we have $f(\mathcal{N})>f(A)$ . We note that for every $e\in Q$ , $f_{A}(e)=f(A+e)-f(A)\leq f(\mathcal{N})-f(A)$ , where the inequality is by monotonicity of the function $f$ . Therefore,

	$\displaystyle q^{*}=\|Q\|$	$\displaystyle\geq\sum_{e\in Q}\left(\frac{f_{A}(e)}{f(\mathcal{N})-f(A)}\right% )\ \ \text{(since $f_{A}(e)\leq f(\mathcal{N})-f(A)$)}$
		$\displaystyle=\frac{\sum_{e\in\mathcal{N}}f_{A}(e)}{f(\mathcal{N})-f(A)}\ \ % \text{(since $f_{A}(e)=0$ for every $e\in A$)}$
		$\displaystyle\geq k^{}.\ \ \text{(by definition of $k^{}$)}\$

$\hfill\blacktriangleleft$

Appendix C Random Sampling gives a Base

In this section, we prove Lemma 6. A variant of the lemma was shown in [2]. See 6

Proof.

If $k^{*}\leq 2\log r$ , then we have $p=1$ , which implies that $S=\mathcal{N}$ which is a base of $f$ . Henceforth, we may assume that $k^{*}>2\log r$ and consequently, $p=\frac{2\log r}{k^{*}}$ . We recall that $n=|\mathcal{N}|$ . Let $\sigma=(e_{1},e_{2},\ldots,e_{n})$ be a uniformly random permutation of the elements in $\mathcal{N}$ . For every $i\in[0,n]$ , we define $\mathcal{N}_{i}:=\{e_{j}:j\in[i]\}$ and $S_{i}:=S\cap\mathcal{N}_{i}$ . We note that $S_{0}=\mathcal{N}_{0}=\emptyset$ and $f_{S_{0}}(\mathcal{N})=r$ .

Let $i\in[n]$ . We consider the distribution of element $e_{i}$ conditioned on $S_{i-1}$ . Since $\sigma$ is a uniformly random permutation, $e_{i}$ can be an arbitrary element in $\mathcal{N}\setminus S_{i-1}$ , of which each has the same probability. That is, for every element $e\in\mathcal{N}$ ,

\displaystyle\mathbf{Pr}_{\sigma,S}[e_{i}=e|S_{i-1}]=

We note that element $e_{i}$ is picked with probability at least $p$ . If element $e_{i}$ is picked, then $S_{i}=S_{i-1}+e_{i}$ . Otherwise, $S_{i}=S_{i-1}$ . Hence, we have

	$\displaystyle\mathbb{E}_{\sigma,S}[f_{S_{i-1}}(\mathcal{N})-f_{S_{i}}(\mathcal% {N})\|S_{i-1}]$	$\displaystyle=\sum_{e\in\mathcal{N}\setminus S_{i-1}}\frac{1}{\|\mathcal{N}\|-\|S% _{i-1}\|}\cdot\mathbb{E}_{\sigma,S}[f_{S_{i-1}}(\mathcal{N})-f_{S_{i}}(\mathcal% {N})\|S_{i-1}\ \text{and}\ e_{i}=e]$
		$\displaystyle\geq\sum_{e\in\mathcal{N}\setminus S_{i-1}}\frac{p}{\|\mathcal{N}\|% -\|S_{i-1}\|}\cdot f_{S_{i-1}}(e)$
		$\displaystyle\geq\frac{p}{n}\cdot\sum_{e\in\mathcal{N}\setminus S_{i-1}}f_{S_{% i-1}}(e)$
		$\displaystyle\geq\frac{p}{n}\cdot k^{*}\cdot f_{S_{i-1}}(\mathcal{N}),$

where the last inequality is by the definition of $k^{*}$ . This implies that

	$\displaystyle\mathbb{E}_{\sigma,S}[f_{S_{i}}(\mathcal{N})]$	$\displaystyle=\mathbb{E}_{\sigma,S}[f_{S_{i-1}}(\mathcal{N})-\mathbb{E}_{% \sigma,S}[f_{\mathcal{S}_{i-1}}(\mathcal{N})-f_{\mathcal{S}_{i}}(\mathcal{N})\|% S_{i-1}]]$
		$\displaystyle\leq\mathbb{E}_{\sigma,S}\left[\left(1-\frac{p}{n}\cdot k^{*}% \right)\cdot f_{S_{i-1}}(\mathcal{N})\right]$
		$\displaystyle=\left(1-\frac{p}{n}\cdot k^{*}\right)\cdot\mathbb{E}_{\sigma,S}[% f_{S_{i-1}}(\mathcal{N})].$

By setting $i=n$ , we have

	$\displaystyle\mathbb{E}_{\sigma,S}[f_{S_{n}}(\mathcal{N})]$	$\displaystyle\leq\left(1-\frac{p}{n}\cdot k^{*}\right)^{n}\cdot\mathbb{E}_{% \sigma,S}[f_{S_{0}}(\mathcal{N})]$
		$\displaystyle=\left(1-\frac{p}{n}\cdot k^{*}\right)^{n}\cdot r$
		$\displaystyle<\exp(-p\cdot k^{*})\cdot r=\exp(-2\log r)\cdot r<\frac{1}{2}.$

According to Markov’s inequality, we have

\displaystyle\mathbf{Pr}_{\sigma,S}[f_{S_{n}}(\mathcal{N})\geq 1]\leq\mathbb{E% }_{\sigma,S}[f_{S_{n}}(\mathcal{N})]<\frac{1}{2},

which shows that $S$ is a base with probability at least $\frac{1}{2}$ . $\hfill\blacktriangleleft$

[bib.bib1] [1] M. Bienkowski, J. Byrka, and $\mathsf{L}$ . Jeż. Online Disjoint Set Covers: Randomization Is Not Necessary. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, pages 18:1–18:16, 2025.

[bib.bib2] [2] G. Călinescu, C. Chekuri, and J. Vondrák. Disjoint bases in a polymatroid. Random Struct. Algorithms, 35(4):418–430, 2009. doi:10.1002/RSA.20274.

[bib.bib3] [3] K. Chandrasekaran, C. Chekuri, and W. Zhu. Online disjoint spanning trees and polymatroid bases. arXiv preprint arXiv:2503.19999, 2025.

[bib.bib4] [4] J. Cheriyan and M. R. Salavatipour. Packing element-disjoint steiner trees. ACM Trans. Algorithms, 3(4):47, 2007. doi:10.1145/1290672.1290684.

[bib.bib5] [5] J. Edmonds. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards B, 69:73–77, 1965.

[bib.bib6] [6] Y. Emek, A. Goldbraikh, and E. Kantor. Online Disjoint Set Cover Without Prior Knowledge. In 27th Annual European Symposium on Algorithms (ESA), pages 44:1–44:16, 2019.

[bib.bib7] [7] U. Feige, M. M. Halldórsson, G. Kortsarz, and A. Srinivasan. Approximating the domatic number. SIAM Journal on Computing, 32(1):172–195, 2002. doi:10.1137/S0097539700380754.

[bib.bib8] [8] S. Fujishige. Theory of principal partitions revisited. Research Trends in Combinatorial Optimization, pages 127–162, 2009.

[bib.bib9] [9] H. Narayanan. The principal lattice of partitions of a submodular function. Linear Algebra and its Applications, 144:179–216, 1991.

[bib.bib10] [10] H. Narayanan. Submodular functions and electrical networks, volume 54. Elsevier, 1997.

[bib.bib11] [11] A. Pananjady, V. K. Bagaria, and R. Vaze. The online disjoint set cover problem and its applications. In 2015 IEEE Conference on Computer Communications (INFOCOM), pages 1221–1229, 2015.

[bib.bib12] [12] K. Quanrud. Quotient sparsification for submodular functions. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5209–5248, 2024.

[bib.bib13] [13] A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003.

	$\displaystyle\mathbb{E}_{\sigma,S}[f_{S_{i-1}}(\mathcal{N})-f_{S_{i}}(\mathcal% {N})\|S_{i-1}]$	$\displaystyle=\sum_{e\in\mathcal{N}\setminus S_{i-1}}\frac{1}{\|\mathcal{N}\|-\|S% _{i-1}\|}\cdot\mathbb{E}_{\sigma,S}[f_{S_{i-1}}(\mathcal{N})-f_{S_{i}}(\mathcal% {N})\|S_{i-1}\ \text{and}\ e_{i}=e]$
		$\displaystyle\geq\sum_{e\in\mathcal{N}\setminus S_{i-1}}\frac{p}{\|\mathcal{N}\|% -\|S_{i-1}\|}\cdot f_{S_{i-1}}(e)$
		$\displaystyle\geq\frac{p}{n}\cdot\sum_{e\in\mathcal{N}\setminus S_{i-1}}f_{S_{% i-1}}(e)$
		$\displaystyle\geq\frac{p}{n}\cdot k^{*}\cdot f_{S_{i-1}}(\mathcal{N}),$

Online Disjoint Spanning Trees and Polymatroid Bases

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Online Disj-Polymatroid-Bases Model.

Applications.

Prior work in the offline setting.

Prior work in the online setting.

1.1 Our Results

Theorem 1.

Theorem 2.

1.2 Technical Background and Overview of Algorithms

Definition 3.

Organization.

2 Preliminaries

Lemma 4 ([12]).

Theorem 5 ([2]).

Lemma 6.

3 An 𝑶⁢(𝐥𝐨𝐠𝟐⁡𝒓)-Competitive Algorithm

3.1 Algorithm Description

3.2 Ordered Min-sized Quotients Property

Lemma 7.

Proof.

3.3 Structural Property

Lemma 8.

Lemma 9.

Proof.

Lemma 10.

Proof.

Corollary 11.

Proof.

Proof of Lemma 8.

3.4 Competitive Ratio Analysis

Lemma 12.

Proof.

Corollary 13.

Proof.

3.5 Combined Algorithm

Theorem 14.

Proof.

4 Approximation of 𝒒𝒕 in Polynomial Time

Strength Decomposition.

Definition 15.

Lemma 16.

Approximating 𝒒𝒕 in Polynomial Time.

Lemma 17.

5 Simpler Algorithm for Online Disj-Conn-Spanning-Subhypergraphs

6 Conclusion

References

Appendix A Quotients for some concrete polymatroids

Appendix B Min-size of a non-empty Quotient and 𝒌∗

Lemma 18.

Proof.

Appendix C Random Sampling gives a Base

Proof.

3 An $O(\log^{2}r)$ -Competitive Algorithm

4 Approximation of $q_{t}$ in Polynomial Time

Approximating $q_{t}$ in Polynomial Time.

Appendix B Min-size of a non-empty Quotient and $k^{*}$