Submodular secretary problems: cardinality, matching, and linear constraints. (English) Zbl 1467.68225
Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 16, 22 p. (2017).
Summary: 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.31\alpha\)-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.207\alpha\)-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^{-\frac{2}{n-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^{-\frac{1}{n-1}})\)-competitive if both \(d\) and \(B\) are known to the algorithm beforehand.
For the entire collection see [Zbl 1372.68012].
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.31\alpha\)-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.207\alpha\)-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^{-\frac{2}{n-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^{-\frac{1}{n-1}})\)-competitive if both \(d\) and \(B\) are known to the algorithm beforehand.
For the entire collection see [Zbl 1372.68012].
MSC:
| 68W27 | Online algorithms; streaming algorithms |
| 68W20 | Randomized algorithms |
| 90C27 | Combinatorial optimization |
References:
| [1] | August 17-19, 2011. Proceedings, pages 218-229, 2011. doi:10.1007/978-3-642-22935-0_19. · Zbl 1343.90077 · doi:10.1007/978-3-642-22935-0_19 |
| [2] | 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. doi:10.1007/978-3-642-23719-5_66. · Zbl 1246.68263 · doi:10.1007/978-3-642-23719-5_66 |
| [3] | 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. doi:10.1137/1.9781611973730.79. · Zbl 1372.68285 · doi:10.1137/1.9781611973730.79 |
| [4] | Moran Feldman and Rico Zenklusen. The submodular secretary problem goes linear. In Proc. 56th Symp. Foundations of Computer Science (FOCS), pages 486-505, 2015. doi: 10.1109/FOCS.2015.37. · Zbl 1390.68769 · doi:10.1109/FOCS.2015.37 |
| [5] | Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non-monotone submodular maximization: Offline and secretary algorithms. In Proc. 6th |
| [6] | Int’l Conf. Web and Internet Economics (WINE), pages 246-257, 2010. doi:10.1007/ 978-3-642-17572-5_20. · doi:10.1007/978-3-642-17572-5_20 |
| [7] | 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. doi:10.1137/1.9781611973105.88. · Zbl 1425.91198 · doi:10.1137/1.9781611973105.88 |
| [8] | 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. doi:10.1007/ 978-3-642-40450-4_50. · Zbl 1394.68448 · doi:10.1007/978-3-642-40450-4_50 |
| [9] | 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. doi:10.1145/2591796.2591810. · Zbl 1315.68291 · doi:10.1145/2591796.2591810 |
| [10] | 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. · Zbl 1297.68268 |
| [11] | 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. doi:10.1145/2746539.2746626. · Zbl 1322.91031 · doi:10.1145/2746539.2746626 |
| [12] | Nitish Korula and Martin Pál. Algorithms for secretary problems on graphs and hyper-graphs. In Proc. 36th Int’l Coll. Autom. Lang. Program. (ICALP), pages 508-520, 2009. doi:10.1007/978-3-642-02930-1_42. · Zbl 1248.68573 · doi:10.1007/978-3-642-02930-1_42 |
| [13] | Andreas Krause and Daniel Gloving. Submodular function maximization. In Tractability: Practical Approaches to Hard Problems, chapter 3. Cambridge University Press, 2014. |
| [14] | Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nonmono-tone submodular maximization with knapsack constraints. Math. Oper. Res., 38(4):729-739, 2013. doi:10.1287/moor.2013.0592. · Zbl 1291.90205 · doi:10.1287/moor.2013.0592 |
| [15] | 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. doi: 10.1109/FOCS.2014.42. · doi:10.1109/FOCS.2014.42 |
| [16] | 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. doi: 10.1287/moor.1100.0463. · Zbl 1216.68342 · doi:10.1287/moor.1100.0463 |
| [17] | 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. doi:10.1007/s00224-015-9642-4. · Zbl 1339.68343 · doi:10.1007/s00224-015-9642-4 |
| [18] | Marco Molinaro and R. Ravi. The geometry of online packing linear programs. Math. Oper. Res., 39(1):46-59, 2014. doi:10.1287/moor.2013.0612. · Zbl 1291.90131 · doi:10.1287/moor.2013.0612 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
