Document Open Access Logo

Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints

Authors Thomas Kesselheim, Andreas Tönnis

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.16.pdf
  • Filesize: 0.55 MB
  • 22 pages

Document Identifiers

Author Details

Thomas Kesselheim
Andreas Tönnis

Cite As Get BibTex

Thomas Kesselheim and Andreas Tönnis. Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.16

Abstract

We study various generalizations of the secretary problem with submodular objective functions. Generally, a set of requests is revealed step-by-step to an algorithm in random order. For each request, one option has to be selected so as to maximize a monotone submodular function while ensuring feasibility. For our results, we assume that we are given an offline algorithm computing an alpha-approximation for the respective problem. This way, we separate computational limitations from the ones due to the online nature. When only focusing on the online aspect, we can assume alpha = 1.

In the submodular secretary problem, feasibility constraints are cardinality constraints, or equivalently, sets are feasible if and only if they are independent sets of a k-uniform matroid. That is, out of a randomly ordered stream of entities, one has to select a subset of size k. For this problem, we present a 0.31alpha-competitive algorithm for all k, which asymptotically reaches competitive ratio alpha/e for large k. In submodular secretary matching, one side of a bipartite graph is revealed online. Upon arrival, each node has to be matched permanently to an offline node or discarded irrevocably. We give a 0.207alpha-competitive algorithm. This also covers the problem, in which sets of entities are feasible if and only if they are independent with respect to a transversal matroid. In both cases, we improve over previously best known competitive ratios, using a generalization of the algorithm for the classic secretary problem.

Furthermore, we give an O(alpha d^(-2/(B-1)))-competitive algorithm for submodular function maximization subject to linear packing constraints. Here, d is the column sparsity, that is the maximal number of none-zero entries in a column of the constraint matrix, and B is the minimal capacity of the constraints. Notably, this bound is independent of the total number of constraints. We improve the algorithm to be O(alpha d^(-1/(B-1)))-competitive if both d and B are known to the algorithm beforehand.

Subject Classification

Keywords
  • Secretary Problem
  • Online Algorithms
  • Submodular Maximization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Shipra Agrawal and Nikhil R. Devanur. Fast algorithms for online stochastic convex programming. In Proc. 26th Symp. Discr. Algorithms (SODA), pages 1405-1424, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.93.
  2. Shipra Agrawal, Zizhuo Wang, and Yinyu Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research, 62(4):876-890, 2014. URL: http://dx.doi.org/10.1287/opre.2014.1289.
  3. Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proc. 18th Symp. Discr. Algorithms (SODA), pages 434-443, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283429.
  4. MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, and Morteza Zadimoghaddam. Submodular secretary problem and extensions. ACM Trans. Algorithms, 9(4):32, 2013. URL: http://dx.doi.org/10.1145/2500121.
  5. Niv Buchbinder and Moran Feldman. Constrained submodular maximization via a non-symmetric technique. CoRR, abs/1611.03253, 2016. URL: http://arxiv.org/abs/1611.03253.
  6. Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proc. 25th Symp. Discr. Algorithms (SODA), pages 1433-1452, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.106.
  7. Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740-1766, 2011. URL: http://dx.doi.org/10.1137/080733991.
  8. Nikhil R. Devenur and Thomas P. Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proc. 10th Conf. Econom. Comput. (EC), pages 71-78, 2009. URL: http://dx.doi.org/10.1145/1566374.1566384.
  9. Alina Ene and Huy L. Nguyen. Constrained submodular maximization: Beyond 1/e. In Proc. 57th Symp. Foundations of Computer Science (FOCS), pages 248-257, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.34.
  10. Moran Feldman and Rani Izsak. Building a good team: Secretary problems and the supermodular degree. In Proc. 28th Symp. Discr. Algorithms (SODA), pages 1651-1670, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.109.
  11. Moran Feldman, Joseph Naor, and Roy Schwartz. Improved competitive ratios for submodular secretary problems (extended abstract). In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings, pages 218-229, 2011. URL: http://dx.doi.org/10.1007/978-3-642-22935-0_19.
  12. Moran Feldman, Joseph Naor, Roy Schwartz, and Justin Ward. Improved approximations for k-exchange systems - (extended abstract). In Proc. 19th European Symp. Algorithms (ESA), pages 784-798, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_66.
  13. Moran Feldman, Ola Svensson, and Rico Zenklusen. A simple O(log log(rank))-competitive algorithm for the matroid secretary problem. In Proc. 26th Symp. Discr. Algorithms (SODA), pages 1189-1201, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.79.
  14. Moran Feldman and Rico Zenklusen. The submodular secretary problem goes linear. In Proc. 56th Symp. Foundations of Computer Science (FOCS), pages 486-505, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.37.
  15. Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non-monotone submodular maximization: Offline and secretary algorithms. In Proc. 6th Int'l Conf. Web and Internet Economics (WINE), pages 246-257, 2010. URL: http://dx.doi.org/10.1007/978-3-642-17572-5_20.
  16. Michael Kapralov, Ian Post, and Jan Vondrák. Online submodular welfare maximization: Greedy is optimal. In Proc. 24th Symp. Discr. Algorithms (SODA), pages 1216-1225, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.88.
  17. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In Proc. 21st European Symp. Algorithms (ESA), pages 589-600, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_50.
  18. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal beats dual on online packing lps in the random-order model. In Proc. 46th Symp. Theory of Computing (STOC), pages 303-312, 2014. URL: http://dx.doi.org/10.1145/2591796.2591810.
  19. Robert D. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proc. 16th Symp. Discr. Algorithms (SODA), pages 630-631, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070519.
  20. Nitish Korula, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Online submodular welfare maximization: Greedy beats 1/2 in random order. In Proc. 47th Symp. Theory of Computing (STOC), pages 889-898, 2015. URL: http://dx.doi.org/10.1145/2746539.2746626.
  21. Nitish Korula and Martin Pál. Algorithms for secretary problems on graphs and hypergraphs. In Proc. 36th Int'l Coll. Autom. Lang. Program. (ICALP), pages 508-520, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02930-1_42.
  22. Andreas Krause and Daniel Gloving. Submodular function maximization. In Tractability: Practical Approaches to Hard Problems, chapter 3. Cambridge University Press, 2014. Google Scholar
  23. Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Math. Oper. Res., 38(4):729-739, 2013. URL: http://dx.doi.org/10.1287/moor.2013.0592.
  24. Oded Lachish. O(log log rank) competitive ratio for the matroid secretary problem. In Proc. 55th Symp. Foundations of Computer Science (FOCS), pages 326-335, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.42.
  25. Jon Lee, Maxim Sviridenko, and Jan Vondrák. Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res., 35(4):795-806, 2010. URL: http://dx.doi.org/10.1287/moor.1100.0463.
  26. Tengyu Ma, Bo Tang, and Yajun Wang. The simulated greedy algorithm for several submodular matroid secretary problems. Theoret. Comput. Sci., 58(4):681-706, 2016. URL: http://dx.doi.org/10.1007/s00224-015-9642-4.
  27. Marco Molinaro and R. Ravi. The geometry of online packing linear programs. Math. Oper. Res., 39(1):46-59, 2014. URL: http://dx.doi.org/10.1287/moor.2013.0612.
  28. George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions - II. Math. Prog., 14(1):265-294, 1978. URL: http://dx.doi.org/10.1007/BF01588971.
  29. G. L. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res., 3(3):177-188, 1978. URL: http://dx.doi.org/10.1287/moor.3.3.177.
  30. Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett., 32(1):41-43, 2004. URL: http://dx.doi.org/10.1016/S0167-6377(03)00062-2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact