Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giảm thiểu cục bộ, chiến thắng toàn cầu: Các khung dựa trên giảm thiểu cho Ghép cặp ngẫu nhiên trực tuyến với thời gian chờ
Tóm tắt
Các bài toán ghép cặp trực tuyến đã thu hút được sự chú ý đáng kể trong những năm gần đây nhờ vào nhiều ứng dụng trong thương mại điện tử, quảng cáo trực tuyến, chia sẻ xe, v.v. Nhiều bài toán trong đó mô tả sự không chắc chắn trong thế giới thực bằng cách đưa vào tính ngẫu nhiên trong cả quá trình đến và quá trình ghép cặp. Bài toán ghép cặp ngẫu nhiên trực tuyến với thời gian chờ được giới thiệu bởi Bansal et al. (Algorithmica, 2012) mô hình hóa các thị trường ghép cặp (ví dụ: E-Bay, Amazon). Người mua đến từ một phân phối với dạng độc lập và đồng phân (i.i.d.) đã biết trên các hồ sơ người mua và có thể được giới thiệu một danh sách các mặt hàng một lần một. Mỗi người mua có một xác suất mua một mặt hàng và có một giới hạn (thời gian chờ) về số lượng mặt hàng mà họ có thể được xuất trình. Bansal et al. (Algorithmica, 2012) đưa ra một thuật toán cạnh tranh 0.12, sau đó được cải tiến bởi Adamczyk et al. (ESA, 2015) lên 0.24. Chúng tôi trình bày một số khung giảm thiểu trực tuyến sử dụng thuật toán cho ghép cặp ngẫu nhiên ngoại tuyến như một hộp đen. Về phía giới hạn trên, chúng tôi chỉ ra rằng một khung kết hợp với một hộp đen thích ứng từ Bansal et al. (Algorithmica, 2012) cho ra một thuật toán trực tuyến gần như gấp đôi tỷ lệ là 0.46. Hơn nữa, các khung giảm thiểu của chúng tôi mở rộng đến bối cảnh tổng quát hơn về tỷ lệ đến phân đoạn cho các đỉnh trực tuyến. Về phía giới hạn dưới, chúng tôi chỉ ra rằng không có một thuật toán nào có thể đạt được tỷ lệ tốt hơn 0.632 khi sử dụng LP tiêu chuẩn cho bài toán này. Khung này có tiềm năng cao cho những cải tiến thêm vì các thuật toán mới cho ghép cặp ngẫu nhiên ngoại tuyến có thể cải thiện trực tiếp tỷ lệ cho bài toán trực tuyến. Các khung trực tuyến của chúng tôi cũng có khả năng mở rộng ra nhiều lĩnh vực khác nhau. Ví dụ, chúng tôi giới thiệu một sự tổng quát tự nhiên: ghép cặp ngẫu nhiên trực tuyến với thời gian chờ hai phía, trong đó cả hai đỉnh trực tuyến và ngoại tuyến đều có thời gian chờ. Các khung của chúng tôi cung cấp thuật toán đầu tiên cho vấn đề này đạt được tỷ lệ là 0.30. Chúng tôi một lần nữa sử dụng thuật toán của Bansal et al. (Algorithmica, 2012) như một hộp đen và tích hợp nó vào một trong những khung của chúng tôi.
Từ khóa
#ghép cặp ngẫu nhiên #trực tuyến #thời gian chờ #thuật toán #giảm thiểuTài liệu tham khảo
Adamczyk, M., Grandoni, F., Mukherjee, J.: Improved approximation algorithms for stochastic matching. In: Bansal, N., Finocchi, I. (eds.) Algorithms—ESA: 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings (Berlin, Heidelberg, 2015), pp. 1–12. Springer, Berlin (2015)
Agrawal, S., Devanur, N.R.: Fast algorithms for online stochastic convex programming. In: Proceedings of the 26th Annual ACM–SIAM Symposium on Discrete Algorithms (Philadelphia, PA, USA, 2015), SODA’15, pp. 1405–1424. Society for Industrial and Applied Mathematics, New York
Agrawal, S., Wang, Z., Ye, Y.: A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4), 876–890 (2014)
Alaei, S., Hajiaghayi, M., Liaghat, V.: Online prophet-inequality matching with applications to ad allocation. In: Proceedings of the 13th ACM Conference on Electronic Commerce (New York, NY, USA, 2012), EC’12, pp. 18–35. ACM, New York
Alaei, S., Hajiaghayi, M., Liaghat, V.: The online stochastic generalized assignment problem. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21–23: Proceedings (Berlin, Heidelberg, 2013), pp. 11–25. Springer, Berlin (2013)
Bahmani, B., Kapralov, M.: Improved bounds for online stochastic matching. In: Algorithms—ESA 2010, pp. 170–181. Springer, Berlin (2010)
Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A.: When LP is the cure for your matching woes: improved bounds for stochastic matchings. In: Algorithms—ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6–8, Proceedings, Part II (Berlin, Heidelberg, 2010), pp. 218–229. Springer, Berlin (2010)
Baveja, A., Chavan, A., Nikiforov, A., Srinivasan, A., Xu, P.: Improved bounds in stochastic matching and optimization. In: APPROX-RANDOM 2015, LIPIcs-Leibniz International Proceedings in Informatics, vol. 40, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)
Brubach, B., Sankararaman, K.A., Srinivasan, A., Xu, P.: New algorithms, better bounds, and a novel model for online stochastic matching. In: European Symposium on Algorithms (ESA) (2016)
Brubach, B., Sankararaman, K.A., Srinivasan, A., Xu, P.: Attenuate locally, win globally: an attenuation-based framework for online stochastic matching with timeouts. In: Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems, pp. 1223–1231 (2017)
Buchbinder, N., Jain, K., Naor, J.S.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: Algorithms—ESA 2007: 15th Annual European Symposium, Eilat, Israel, October 8–10, Proceedings (Berlin, Heidelberg, 2007), pp. 253–264. Springer, Berlin (2007)
Chen, N., Immorlica, N., Karlin, A.R., Mahdian, M., Rudra, A.: Approximating matches made in heaven. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming, LNCS 5555, pp. 266–278 (2009)
Devanur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: Proceedings of the 10th ACM Conference on Electronic Commerce (2009), pp. 71–78. ACM, New York
Devanur, N.R., Jain, K.: Online matching with concave returns. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pp. 137–144. ACM, New York (2012)
Devanur, N.R., Jain, K., Sivan, B., Wilkens, C.A.: Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In: Proceedings of the 12th ACM Conference on Electronic Commerce (New York, NY, USA, 2011), EC’11, pp. 29–38. ACM, New York
Devanur, N.R., Sivan, B., Azar, Y.: Asymptotically optimal algorithm for stochastic adwords. In: Proceedings of the 13th ACM Conference on Electronic Commerce, EC’12 (2012)
Feldman, J., Henzinger, M., Korula, N., Mirrokni, V.S., Stein, C.: Online stochastic packing applied to display ad allocation. In: Proceedings of the 18th Annual European Conference on Algorithms: Part I (Berlin, Heidelberg, 2010), ESA’10, pp. 182–194. Springer, Berlin
Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: Beating 1-1/e. In: FOCS’09. 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 117–126. IEEE, New York (2009)
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM (JACM) 53(3), 324–360 (2006)
Gupta, A., Nagarajan, V.: A stochastic probing problem with applications. In: Integer Programming and Combinatorial Optimization: 16th International Conference, IPCO 2013, Valparaíso, Chile, March 18–20: Proceedings (Berlin, Heidelberg, 2013), pp. 205–216. Springer, Berlin (2013)
Haeupler, B., Mirrokni, V.S., Zadimoghaddam, M.: Online stochastic weighted matching: improved approximation algorithms. In: Internet and Network Economics, vol. 7090 of Lecture Notes in Computer Science, pp. 170–181. Springer, Berlin (2011)
Jaillet, P., Lu, X.: Online stochastic matching: new algorithms with better bounds. Math. Oper. Res. 39(3), 624–646 (2013)
Kalyanasundaram, B., Pruhs, K.R.: An optimal deterministic algorithm for online \(b\)-matching. Theoret. Comput. Sci. 233, 2000 (2000)
Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 352–358. ACM, New York (1990)
Ma, W.: Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms. In: Proceedings of the 25th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 1154–1163. Society for Industrial and Applied Mathematics, New York (2014)
Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: online actions based on offline statistics. Math. Oper. Res. 37(4), 559–573 (2012)
Mehta, A.: Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4), 265–368 (2012)
Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. J. ACM 54, 5 (2007)