Matroid Secretary Problems

被引：22

作者：

Babaioff, Moshe ^{[1
,5
]}

Immorlica, Nicole ^{[2
]}

Kempe, David ^{[3
]}

Kleinberg, Robert ^{[4
]}

机构：

[1] Microsoft Res, Herzliyya, Israel

[2] Microsoft Res, 1 Mem Dr, Cambridge, MA 02142 USA

[3] Univ Southern Calif, Dept Comp Sci, Los Angeles, CA 90089 USA

[4] Cornell Univ, Dept Comp Sci, Ithaca, NY 14853 USA

[5] Microsoft, 13 Shenkar St, IL-4672513 Herzliyya, Israel

来源：

JOURNAL OF THE ACM | 2018年 / 65卷 / 06期

关键词：

Secretary problem; matroids; online algorithms; mechanism design; competitive ratio;

D O I：

10.1145/3212512

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页数：26

共 42 条

[1] LOW-DISTORTION INFERENCE OF LATENT SIMILARITIES FROM A MULTIPLEX SOCIAL NETWORK [J].

Abraham, Ittai ;

Chechik, Shiri ;

Kempe, David ;

Slivkins, Aleksandrs .

SIAM JOURNAL ON COMPUTING, 2015, 44 (03) :617-668

[2]

[Anonymous], 2012, P ACM C EL COMM EC

[3]

[Anonymous], 1963, Soviet Math.

[4]

[Anonymous], 2014, SODA 14, DOI [10.1137/1.9781611973730.79,arXiv:https://epubs.siam, DOI 10.1137/1.9781611973730.79,ARXIV:HTTPS://EPUBS.SIAM]

[5]

Babaioff M., 2005, AAAI, V5, P241

[6]

Babaioff M, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P434

[7]

Babaioff M, 2007, LECT NOTES COMPUT SC, V4627, P16

[8]

Barman S, 2012, LECT NOTES COMPUT SC, V7391, P75, DOI 10.1007/978-3-642-31594-7_7

[9]

Bateni M, 2010, LECT NOTES COMPUT SC, V6302, P39, DOI 10.1007/978-3-642-15369-3_4

[10]

Buchbinder N, 2010, LECT NOTES COMPUT SC, V6080, P163, DOI 10.1007/978-3-642-13036-6_13

← 1 2 3 4 5 →