Secretary problems with non-uniform arrival order. (English) Zbl 1321.68516
Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 879-888 (2015).
MSC:
| 68W27 | Online algorithms; streaming algorithms |
| 68Q25 | Analysis of algorithms and problem complexity |
Citations:
Zbl 1248.68573Software:
GraphsReferences:
| [1] | Agrawal, S. and Devanur, N. (2015). Fast algorithms for online stochastic convex programming. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms. |
| [2] | Agrawal, S., Wang, Z., and Ye, Y. (2014). A dynamic near-optimal algorithm for online linear programming. Operations Research, 62:867-890. 10.1287/opre.2014.1289 · Zbl 1302.90119 |
| [3] | Babaioff, M., Immorlica, N., Kempe, D., and Kleinberg, R. (2007a). A knapsack secretary problem with applications. In Proc. 2007 Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX), pages 16-28. Springer. 10.1007/978-3-540-74208-1_2 · Zbl 1171.90417 |
| [4] | Babaioff, M., Immorlica, N., and Kleinberg, R. (2007b). Matroids, secretary problems, and online mechanisms. In Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 434-443. · Zbl 1302.68133 |
| [5] | Baraniuk, R., Davenport, M., DeVore, R., and Wakin, M. (2008). A simple proof of the restricted isometry property for random matrices. Constructive Approximation, 28(3):253-263. · Zbl 1177.15015 |
| [6] | Bateni, M., Hajiaghayi, M., and Zadimoghaddam, M. (2013). Submodular secretary problem and extensions. ACM Transactions on Algorithms (TALG), 9(4):32. 10.1145/2500121 · Zbl 1301.91016 |
| [7] | Candes, E. J. and Tao, T. (2005). Decoding by linear programming. IEEE Trans. Information Theory, 51(12):4203-4215. 10.1109/TIT.2005.858979 · Zbl 1264.94121 |
| [8] | Carothers, N. L. (2009). A short course on approximation theory. http://personal.bgsu.edu/ carother/Approx.html. Manuscript. |
| [9] | Devanur, N. and Hayes, T. P. (2009). The AdWords problem: Online keyword matching with budgeted bidders under random permutations. In Proc. 10th ACM Conference on Electronic Commerce, pages 71-78. 10.1145/1566374.1566384 |
| [10] | Devanur, N. R., Jain, K., Sivan, B., and Wilkens, C. A. (2011). Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In Proc. 12th ACM Conference on Electronic Commerce, pages 29-38. ACM. 10.1145/1993574.1993581 |
| [11] | Dimitrov, N. B. and Plaxton, C. G. (2012). Competitive weighted matching in transversal matroids. Algorithmica, 62(1-2):333-348. 10.1007/s00453-010-9457-2 · Zbl 1239.05148 |
| [12] | Dynkin, E. B. (1963). The optimum choice of the instant for stopping a Markov process. Sov. Math. Dokl., 4. |
| [13] | Feldman, J., Henzinger, M., Korula, N., Mirrokni, V. S., and Stein, C. (2010). Online stochastic packing applied to display ad allocation. In Algorithms-ESA 2010, pages 182-194. Springer. · Zbl 1287.68186 |
| [14] | Feldman, M., Naor, J. S., and Schwartz, R. (2011). Improved competitive ratios for submodular secretary problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 218-229. Springer. |
| [15] | Feldman, M., Svensson, O., and Zenklusen, R. (2015). A simple O(log log(rank))-competitive algorithm for the matroid secretary problem. In Proc. 25th Annual ACM-SIAM Symposium on Discrete Algorithms. |
| [16] | Göbel, O., Hoefer, M., Kesselheim, T., Schleiden, T., and Vöcking, B. (2014). Online independent set beyond the worst-case: Secretaries, prophets, and periods. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 508-519. · Zbl 1409.68342 |
| [17] | Hajiaghayi, M. T., Kleinberg, R., and Parkes, D. C. (2004). Adaptive limited-supply online auctions. In Proc. 5th ACM conference on Electronic commerce, pages 71-80. ACM Press. 10.1145/988772.988784 |
| [18] | Jaillet, P., Soto, J. A., and Zenklusen, R. (2013). Advances on matroid secretary problems: Free order model and laminar case. In Integer Programming and Combinatorial Optimization, pages 254-265. Springer. 10.1007/978-3-642-36694-9_22 · Zbl 1372.90093 |
| [19] | Kaplan, E., Naor, M., and Reingold, O. (2009). Derandomized constructions of k-wise (almost) independent permutations. Algorithmica, 55(1):113-133. 10.1007/s00453-008-9267-y · Zbl 1180.68200 |
| [20] | Kesselheim, T., Radke, K., Tönnis, A., and Vöcking, B. (2013). An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In Algorithms-ESA 2013, pages 589-600. Springer. · Zbl 1394.68448 |
| [21] | Kesselheim, T., Radke, K., Tönnis, A., and Vöcking, B. (2014). Primal beats dual on online packing LPs in the random-order model. In Proc. ACM Symposium on Theory of Computing, pages 303-312. 10.1145/2591796.2591810 · Zbl 1315.68291 |
| [22] | Kleinberg, R. D. (2005). A multiple-choice secretary algorithm with applications to online auctions. In Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 630-631. · Zbl 1297.68268 |
| [23] | 2009 · Zbl 1248.68573 |
| [24] | Lachish, O. (2014). O(log log rank) competitive-ratio for the matroid secretary problem (the known cardinality variant). In Proc.55th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 10.1109/FOCS.2014.42 |
| [25] | Lindley, D. V. (1961). Dynamic programming and decision theory. Applied Statistics, 10:39-51. · Zbl 0114.34904 |
| [26] | Meyerson, A. (2001). Online facility location. In Proc. 42nd Annual Symposium on Foundations of Computer Science, pages 426-431. |
| [27] | Meyerson, A., Munagala, K., and Plotkin, S. A. (2001). Designing networks incrementally. In Proc. 42nd Annual Symposium on Foundations of Computer Science, pages 406-415. |
| [28] | Mitzenmacher, M. and Vadhan, S. (2008). Why simple hash functions work: exploiting the entropy in a data stream. In Proc. 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 746-755. Society for Industrial and Applied Mathematics. · Zbl 1192.68202 |
| [29] | Molinaro, M. and Ravi, R. (2015). The geometry of online packing linear programs. Math. of Operations Research. to appear. 10.1287/moor.2013.0612 |
| [30] | Roughgarden, T. and Trevisan, L. (2011). Workshop on beyond worst-case analysis. Stanford University, September 2011. http://theory.stanford.edu/ tim/bwca/bwca.html. |
| [31] | Samuels, S. M. (1981). Minimax stopping rules when the underlying distribution is uniform. J. Amer. Statist. Assoc., 76:188-197. · Zbl 0459.62070 |
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.
