The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems

详细信息    查看全文

• 作者：Tengyu Ma ; Bo Tang ; Yajun Wang
• 关键词：Secretary problem ; Submodular function ; Matroid
• 刊名：Theory of Computing Systems
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：58
• 期：4
• 页码：681-706
• 全文大小：819 KB
• 参考文献：1.Babaioff, M., Dinitz, M., Gupta, A., Immorlica, N., Talwar, K.: Secretary problems: weights and discounts. In: SODA, pp 1245–1254 (2009)
  2.Bateni, M.H., Hajiaghayi, M.T., Zadimoghaddam, M.: Submodular secretary problem and extensions. ACM Trans. Algorithms 9(4), 32 (2013)MathSciNet CrossRef MATH
  3.Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: SODA, pp 434–443 (2007)
  4.Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: APPROX-RANDOM, pp 16–28 (2007)
  5.Chakraborty, S., Lachish, O.: Improved competitive ratio for the matroid secretary problem. In: SODA, pp 1702–1712 (2012)
  6.Dinitz, M., Kortsarz, G.: Matroid secretary for regular and decomposable matroids. SIAM J. Comput. 43(5), 1807–1830 (2014)MathSciNet CrossRef MATH
  7.Dimitrov, N.B., Plaxton, C.G.: Competitive weighted matching in transversal matroids. Algorithmica 62(1-2), 333–348 (2012)MathSciNet CrossRef MATH
  8.Dynkin, E.B.: Optimal choice of the stopping moment of a markov process. Dokl. Akad. Nauk SSSR 150, 238–240 (1963)MathSciNet
  9.Ferguson, T.S.: Who solved the secretary problem Stat. Sci. 4, 282–289 (1989)MathSciNet CrossRef MATH
  10.Feldman, M., Naor, J. (Seffi), Schwartz, R.: Improved competitive ratios for submodular secretary problems (extended abstract). In: APPROX-RANDOM, pp 218–229 (2011)
  11.Fisher, M. L., Nemhauser, G. L., Wolsey, L. A.: An analysis of approximations for maximizing submodular set functions — II. In: Polyhedral combinatorics of mathematical programming studies, vol. 8, pp 73–87. Springer, Berlin Heidelberg (1978)
  12.Freeman, P R: The secretary problem and its extensions: A review, International Statistical Review (1983)
  13.Moran Feldman, Ola Svensson, Rico Zenklusen: A simple O(log log(rank))-competitive algorithm for the matroid secretary problem. In: Piotr Indyk (ed.) Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pp 1189–1201. SIAM (2015)
  14.Gardner, M.: Mathematical games column. Sci. Am., 35 (1960)
  15.Gupta, A., Roth, A., Schoenebeck, G., Talwar, K.: Constrained non-monotone submodular maximization: offline and secretary algorithms. In: WINE, pp 246–257 (2010)
  16.Gharan, S. O., Vondrȧk, J.: On variants of the matroid secretary problem. Algorithmica 67(4), 472–497 (2013)MathSciNet CrossRef MATH
  17.Im, S., Wang, Y.: Secretary problems: Laminar matroid and interval scheduling. In: Randall, D. (ed.) Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pp 1265–1274. SIAM (2011)
  18.Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: SODA, pp 630–631, Philadelphia (2005)
  19.Korula, N., Pál, M.: Algorithms for secretary problems on graphs and hypergraphs. In: ICALP (2), pp 508–520 (2009)
  20.Lachish, O.: O(log log rank) competitive-ratio for the matroid secretary problem. arXiv:1403.​7343 (2014)
  21.Soto, J.A.: Matroid secretary problem in the random-assignment model. SIAM J. Comput. 42(1), 178–211 (2013)MathSciNet CrossRef MATH
  
• 作者单位：Tengyu Ma (1)
  Bo Tang (2)
  Yajun Wang (3)
  
  1. Princeton University, Princeton, NJ, 08540, USA
  2. University of Liverpool, Liverpool, L69 3BX, UK
  3. Microsoft Cooperation, Sunnyvale, CA, 94089, USA
  
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1433-0490

文摘

We study the matroid secretary problems with submodular valuation functions. In these problems, the elements arrive in random order. When one element arrives, we have to make an immediate and irrevocable decision on whether to accept it or not. The set of accepted elements must form an independent set in a predefined matroid. Our objective is to maximize the value of the accepted elements. In this paper, we focus on the case that the valuation function is a non-negative and monotonically non-decreasing submodular function. We introduce a general algorithm for such submodular matroid secretary problems. In particular, we obtain constant competitive algorithms for the cases of laminar matroids and transversal matroids. Our algorithms can be further applied to any independent set system defined by the intersection of a constant number of laminar matroids, while still achieving constant competitive ratios. Notice that laminar matroids generalize uniform matroids and partition matroids. On the other hand, when the underlying valuation function is linear, our algorithm achieves a competitive ratio of 9.6 for laminar matroids, which significantly improves the previous result.