{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T19:23:51Z","timestamp":1774034631590,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,7,13]],"date-time":"2019-07-13T00:00:00Z","timestamp":1562976000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,13]],"date-time":"2019-07-13T00:00:00Z","timestamp":1562976000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1010789"],"award-info":[{"award-number":["1010789"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1422569"],"award-info":[{"award-number":["1422569"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1749864"],"award-info":[{"award-number":["1749864"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004344","name":"Adobe Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00453-019-00603-7","type":"journal-article","created":{"date-parts":[[2019,7,13]],"date-time":"2019-07-13T05:21:56Z","timestamp":1562995316000},"page":"64-87","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Attenuate Locally, Win Globally: Attenuation-Based Frameworks for Online Stochastic Matching with Timeouts"],"prefix":"10.1007","volume":"82","author":[{"given":"Brian","family":"Brubach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8569-5694","authenticated-orcid":false,"given":"Karthik A.","family":"Sankararaman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,13]]},"reference":[{"key":"603_CR1","unstructured":"Adamczyk, M., Grandoni, F., Mukherjee, J.: Improved approximation algorithms for stochastic matching. In: Bansal, N., Finocchi, I. (eds.) Algorithms\u2014ESA: 23rd Annual European Symposium, Patras, Greece, September 14\u201316, 2015, Proceedings (Berlin, Heidelberg, 2015), pp. 1\u201312. Springer, Berlin (2015)"},{"key":"603_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal, S., Devanur, N.R.: Fast algorithms for online stochastic convex programming. In: Proceedings of the 26th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (Philadelphia, PA, USA, 2015), SODA\u201915, pp. 1405\u20131424. Society for Industrial and Applied Mathematics, New York","DOI":"10.1137\/1.9781611973730.93"},{"issue":"4","key":"603_CR3","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1287\/opre.2014.1289","volume":"62","author":"S Agrawal","year":"2014","unstructured":"Agrawal, S., Wang, Z., Ye, Y.: A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4), 876\u2013890 (2014)","journal-title":"Oper. Res."},{"key":"603_CR4","unstructured":"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\u201912, pp. 18\u201335. ACM, New York"},{"key":"603_CR5","unstructured":"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\u201323: Proceedings (Berlin, Heidelberg, 2013), pp. 11\u201325. Springer, Berlin (2013)"},{"key":"603_CR6","doi-asserted-by":"crossref","unstructured":"Bahmani, B., Kapralov, M.: Improved bounds for online stochastic matching. In: Algorithms\u2014ESA 2010, pp. 170\u2013181. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-15775-2_15"},{"key":"603_CR7","unstructured":"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\u2014ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6\u20138, Proceedings, Part II (Berlin, Heidelberg, 2010), pp. 218\u2013229. Springer, Berlin (2010)"},{"key":"603_CR8","unstructured":"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.\u00a040, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)"},{"key":"603_CR9","unstructured":"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)"},{"key":"603_CR10","unstructured":"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\u20131231 (2017)"},{"key":"603_CR11","unstructured":"Buchbinder, N., Jain, K., Naor, J.S.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: Algorithms\u2014ESA 2007: 15th Annual European Symposium, Eilat, Israel, October 8\u201310, Proceedings (Berlin, Heidelberg, 2007), pp. 253\u2013264. Springer, Berlin (2007)"},{"key":"603_CR12","doi-asserted-by":"crossref","unstructured":"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\u2013278 (2009)","DOI":"10.1007\/978-3-642-02927-1_23"},{"key":"603_CR13","doi-asserted-by":"crossref","unstructured":"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\u201378. ACM, New York","DOI":"10.1145\/1566374.1566384"},{"key":"603_CR14","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K.: Online matching with concave returns. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pp. 137\u2013144. ACM, New York (2012)","DOI":"10.1145\/2213977.2213992"},{"key":"603_CR15","unstructured":"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\u201911, pp. 29\u201338. ACM, New York"},{"key":"603_CR16","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Sivan, B., Azar, Y.: Asymptotically optimal algorithm for stochastic adwords. In: Proceedings of the 13th ACM Conference on Electronic Commerce, EC\u201912 (2012)","DOI":"10.1145\/2229012.2229043"},{"key":"603_CR17","unstructured":"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\u201910, pp. 182\u2013194. Springer, Berlin"},{"key":"603_CR18","unstructured":"Feldman, J., Mehta, A., Mirrokni, V., Muthukrishnan, S.: Online stochastic matching: Beating 1-1\/e. In: FOCS\u201909. 50th Annual IEEE Symposium on Foundations of Computer Science, 2009, pp. 117\u2013126. IEEE, New York (2009)"},{"issue":"3","key":"603_CR19","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/1147954.1147956","volume":"53","author":"R Gandhi","year":"2006","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM (JACM) 53(3), 324\u2013360 (2006)","journal-title":"J. ACM (JACM)"},{"key":"603_CR20","unstructured":"Gupta, A., Nagarajan, V.: A stochastic probing problem with applications. In: Integer Programming and Combinatorial Optimization: 16th International Conference, IPCO 2013, Valpara\u00edso, Chile, March 18\u201320: Proceedings (Berlin, Heidelberg, 2013), pp. 205\u2013216. Springer, Berlin (2013)"},{"key":"603_CR21","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Mirrokni, V.S., Zadimoghaddam, M.: Online stochastic weighted matching: improved approximation algorithms. In: Internet and Network Economics, vol.\u00a07090 of Lecture Notes in Computer Science, pp. 170\u2013181. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-25510-6_15"},{"issue":"3","key":"603_CR22","doi-asserted-by":"publisher","first-page":"624","DOI":"10.1287\/moor.2013.0621","volume":"39","author":"P Jaillet","year":"2013","unstructured":"Jaillet, P., Lu, X.: Online stochastic matching: new algorithms with better bounds. Math. Oper. Res. 39(3), 624\u2013646 (2013)","journal-title":"Math. Oper. Res."},{"key":"603_CR23","doi-asserted-by":"publisher","first-page":"2000","DOI":"10.1016\/S0304-3975(99)00140-1","volume":"233","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.R.: An optimal deterministic algorithm for online $$b$$-matching. Theoret. Comput. Sci. 233, 2000 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"603_CR24","doi-asserted-by":"crossref","unstructured":"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\u2013358. ACM, New York (1990)","DOI":"10.1145\/100216.100262"},{"key":"603_CR25","doi-asserted-by":"crossref","unstructured":"Ma, W.: Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms. In: Proceedings of the 25th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 1154\u20131163. Society for Industrial and Applied Mathematics, New York (2014)","DOI":"10.1137\/1.9781611973402.85"},{"issue":"4","key":"603_CR26","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1287\/moor.1120.0551","volume":"37","author":"VH Manshadi","year":"2012","unstructured":"Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: online actions based on offline statistics. Math. Oper. Res. 37(4), 559\u2013573 (2012)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"603_CR27","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1561\/0400000057","volume":"8","author":"A Mehta","year":"2012","unstructured":"Mehta, A.: Online matching and ad allocation. Found. Trends Theor. Comput. Sci. 8(4), 265\u2013368 (2012)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"603_CR28","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/1284320.1284321","volume":"54","author":"A Mehta","year":"2007","unstructured":"Mehta, A., Saberi, A., Vazirani, U., Vazirani, V.: Adwords and generalized online matching. J. ACM 54, 5 (2007)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00603-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00603-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00603-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,11]],"date-time":"2020-07-11T23:14:21Z","timestamp":1594509261000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00603-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,13]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["603"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00603-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,13]]},"assertion":[{"value":"4 May 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}