摘要 Abstract
在给定图中寻找最大数量的不相交生成树是一个被广泛研究的问题,具有多种应用和联系。Tutte-Nash-Williams定理为此问题提供了最小-最大关系,并推广到拟阵中的不相交基,从而得到高效的算法。其他一些包装问题如元素不相交的Steiner树、不相交集覆盖以及不相交支配集等问题是NP困难的,但可以得到$O(\log n)$-近似解。Cǎlinescu、Chekuri和Vondr'ak将所有这些包装问题视为拟阵基的包装,并提供了一个统一的观点。受无线网络应用的启发,近期的研究工作探讨了在线模型下集合覆盖的包装问题。在线模型为包装问题带来了新的挑战。特别是,当边以在线方式到达时,如何在图中包装最大数量的不相交生成树尚不清楚。受这些应用和理论考虑的推动,我们制定了拟阵基在线包装的一个模型,并描述了一个具有对数级竞争比的随机算法。我们的算法基于拟阵商的概念,这一概念最近在拟阵稀疏化中得到了应用。我们推广了之前已知的在线不相交集覆盖问题的结果,并以统一的方式处理了多个其他包装问题。对于图(或超图)中边以在线方式到达时的最大不相交生成树包装这一特殊情况,我们提供了一种相对于一般算法更简单且更快的替代方案,同时保持相同的对数级竞争比。
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\u{a}linescu, Chekuri, and Vondr\'ak 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. 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. We generalize the previously known result for the online disjoint set cover problem 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.