Matroid Secretary for Regular and Decomposable Matroids
Matroid Secretary for Regular and Decomposable Matroids
复制标题
常规和可分解拟阵秘书
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
G. Kortsarz
中科院分区：
文献类型：
--
作者：
M. Dinitz;G. Kortsarz
在Matroid秘书问题中，我们将为我们提供了一系列元素，并要求选择一组元素，以最大化集合的总价值，但要作为预先给出的独立的矩阵集合。困难来自以下假设：决策是不可撤销的：如果我们选择在流时接受元素，那么我们将永远无法摆脱它，如果我们选择不接受它，那么我们稍后不能添加它。 Babaioff，Immorlica和Kleinberg [Soda 2007]引入了此问题，给出了某些类型的矩形的O（1）竞争性算法，并猜想每个矩形都可以接受O（1）竞争性算法。但是，大多数已知可以使用图形（例如图形和横向矩阵）轻松表示o（1） - 竞争算法的曲霉。特别是，关于F-代表性的矩形（可以表示为field f上的矢量空间元素，这是基础矩阵类别之一）的鲜为人知的。此外，大多数已知技术都取决于图理论，就像它们相对于Matroid理论。我们通过给出常规曲霉（在每个字段中代表的矩形类别）的O（1） - 竞争算法的o（1） - 竞争算法，并使用原始理论而不是图理论的技术。我们使用seymour的常规基质分解定理将任何常规的矩阵分解为图形，cograwhic或imormorphic to r_ {10}，然后展示如何将这些基本类别的算法组合成常规矩阵的算法。这使我们能够将常规矩阵超越常规的矩阵概括，这些矩阵将这种分解为我们已经具有良好算法的类别。特别是，我们给出了Max-Flow Min-CUT基曲面类别的O（1） - 竞争算法。
In the matroid secretary problem we are given a stream of elements and asked to choose a set of elements that maximizes the total value of the set, subject to being an independent set of a matroid given in advance. The difficulty comes from the assumption that decisions are irrevocable: if we choose to accept an element when it is presented by the stream then we can never get rid of it, and if we choose not to accept it then we cannot later add it. Babaioff, Immorlica, and Kleinberg [SODA 2007] introduced this problem, gave O(1)-competitive algorithms for certain classes of matroids, and conjectured that every matroid admits an O(1)-competitive algorithm. However, most matroids that are known to admit an O(1)-competitive algorithm can be easily represented using graphs (e.g. graphic and transversal matroids). In particular, there is very little known about F-representable matroids (the class of matroids that can be represented as elements of a vector space over a field F), which are one of the foundational matroid classes. Moreover, most of the known techniques are as dependent on graph theory as they are on matroid theory. We go beyond graphs by giving an O(1)-competitive algorithm for regular matroids (the class of matroids that are representable over every field), and use techniques that are matroid-theoretic rather than graph-theoretic. We use the regular matroid decomposition theorem of Seymour to decompose any regular matroid into matroids which are either graphic, cographic, or isomorphic to R_{10}, and then show how to combine algorithms for these basic classes into an algorithm for regular matroids. This allows us to generalize beyond regular matroids to any class of matroids that admits such a decomposition into classes for which we already have good algorithms. In particular, we give an O(1)-competitive algorithm for the class of max-flow min-cut matroids.