Matroid secretary problem in the random assignment model
Matroid secretary problem in the random assignment model
复制标题
随机分配模型中的拟阵秘书问题
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
J. A. Soto
中科院分区：
文献类型：
--
作者：
J. A. Soto
在 Babaioff 等人提出的拟阵秘书问题中。 [5]，给定拟阵的元素以随机顺序呈现给在线算法。当一个元素被揭示时，算法会学习它的权重并决定是否选择它。目标是返回最大权重独立的拟阵集。根据事先已知的权重信息，该问题有不同的变体。
在随机分配模型中，隐藏的权重列表被随机分配给拟阵地面集，与向算法显示的随机顺序无关。我们的主要成果是针对该版本问题的第一个恒定竞争算法，解决了 Babaioff 等人的开放问题。我们的算法实现了 2e2/(e − 1) 的竞争比。它利用了拟阵主分区的概念，将其分解为均匀密集的次要矩阵，以及我们还开发的均匀密集拟阵的 2e 竞争算法。
我们还在标准模型中提出了恒定的竞争算法，其中权重是对抗性分配的，适用于各种类别的拟阵，包括图形、低密度、k 列稀疏线性拟阵以及每个元素都在小型联合电路中的情况。在同一模型中，我们为等级 r 的拟阵提供了一种新的 O(log r) 竞争算法，该算法仅使用所见权重的相对顺序，而不是其实际值，如之前所需要的。
In the Matroid Secretary Problem, introduced by Babaioff et al. [5], the elements of a given matroid are presented to an online algorithm in random order. When an element is revealed, the algorithm learns its weight and decides whether or not to select it. The objective is to return a maximum weight independent set of the matroid. There are different variants for this problem depending on the information known about the weights beforehand.
In the random assignment model, a hidden list of weights is randomly assigned to the matroid ground set, independently from the random order they are revealed to the algorithm. Our main result is the first constant competitive algorithm for this version of the problem, solving an open question of Babaioff et al. Our algorithm achieves a competitive ratio of 2e2/(e − 1). It exploits the notion of principal partition of a matroid, its decomposition into uniformly dense minors, and a 2e-competitive algorithm for uniformly dense matroids we also develop.
We also present constant competitive algorithms in the standard model where the weights are assigned adversarially, for various classes of matroids including cographic, low density, k-column sparse linear matroids and the case when every element is in a small cocircuit. In the same model, we give a new O(log r)-competitive algorithm for matroids of rank r which only uses the relative order of the weights seen and not their actual values, as previously needed.