Matroid Secretary Problems
Matroid Secretary Problems
复制标题
DOI：
10.1145/3212512
复制
发表时间：
2018-11-01
影响因子：
2.5
通讯作者：
Kleinberg, Robert
中科院分区：
文献类型：
--
作者：
Babaioff, Moshe;Immorlica, Nicole;Kleinberg, Robert
我们定义了经典秘书问题的概括，称为Matroid秘书问题。在此问题中，矩阵的元素以统一的随机顺序呈现到在线算法中。当元素到达时，该算法会观察其价值，并且必须做出不可撤销的决定。公认的元素必须形成一个独立的集合，目的是最大化这些元素的合并价值。我们提出了一种通用矩形的O（log k） - 竞争算法（其中k是矩形的等级），以及几种特殊情况，包括图形矩阵，截断的矩形矩形和有界的程度横向矩形的恒定竞争算法。我们将其留作一个悬而未决的问题，即一般矩形的恒定竞争算法的存在。我们的结果在福利最大化在线机制设计领域的应用程序中，同时令人满意的代理形成了矩阵。
We define a generalization of the classical secretary problem called the matroid secretary problem. In this problem, the elements of a matroid are presented to an online algorithm in uniformly random order. When an element arrives, the algorithm observes its value and must make an irrevocable decision whether or not to accept it. The accepted elements must form an independent set, and the objective is to maximize the combined value of these elements. We present an O(log k)-competitive algorithm for general matroids (where k is the rank of the matroid), and constant-competitive algorithms for several special cases including graphic matroids, truncated partition matroids, and bounded degree transversal matroids. We leave as an open question the existence of constant-competitive algorithms for general matroids. Our results have applications in welfare-maximizing online mechanism design for domains in which the sets of simultaneously satisfiable agents form a matroid.