{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T15:27:52Z","timestamp":1725809272783},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319126906"},{"type":"electronic","value":"9783319126913"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12691-3_30","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:11:32Z","timestamp":1415981492000},"page":"395-411","source":"Crossref","is-referenced-by-count":1,"title":["The Power of Rejection in Online Bottleneck Matching"],"prefix":"10.1007","author":[{"given":"Barbara M.","family":"Anthony","sequence":"first","affiliation":[]},{"given":"Christine","family":"Chung","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"issue":"1","key":"30_CR1","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/s10878-012-9581-9","volume":"27","author":"BM Anthony","year":"2014","unstructured":"Anthony, B.M., Chung, C.: Online bottleneck matching. J. Comb. Optim. 27(1), 100\u2013114 (2014)","journal-title":"J. Comb. Optim."},{"key":"30_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-78773-0_20","volume-title":"LATIN 2008: Theoretical Informatics","author":"C Chung","year":"2008","unstructured":"Chung, C., Pruhs, K., Uthaisombut, P.: The online transportation problem: on the exponential boost of one extra server. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 228\u2013239. Springer, Heidelberg (2008)"},{"key":"30_CR3","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, EC \u201909, pp. 71\u201378 (2009). ISBN: 978-1-60558-458-4"},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.tcs.2013.08.022","volume":"540\u2013541","author":"CG Fernandes","year":"2014","unstructured":"Fernandes, C.G., Schouery, R.C.: Second-price ad auctions with binary bids and markets with good competition. Theor. Comput. Sci. 540\u2013541, 103\u2013114 (2014). ISSN: 0304\u20133975","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"30_CR5","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.tcs.2004.10.028","volume":"332","author":"B Fuchs","year":"2005","unstructured":"Fuchs, B., Hochst\u00e4ttler, W., et al.: Online matching on a line. Theor. Comput. Sci. 332(1\u20133), 251\u2013264 (2005). ISSN: 0304\u20133975","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"30_CR6","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/0196-6774(88)90031-4","volume":"9","author":"HN Gabow","year":"1988","unstructured":"Gabow, H.N., Tarjan, R.E.: Algorithms for two bottleneck optimization problems. J. Algorithms 9(3), 411\u2013417 (1988)","journal-title":"J. Algorithms"},{"issue":"7","key":"30_CR7","doi-asserted-by":"publisher","first-page":"1747","DOI":"10.1287\/opre.19.7.1747","volume":"19","author":"RS Garfinkel","year":"1971","unstructured":"Garfinkel, R.S.: An improved algorithm for the bottleneck assignment problem. Oper. Res. 19(7), 1747\u20131751 (1971)","journal-title":"Oper. Res."},{"key":"30_CR8","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201908, pp. 982\u2013991 (2008)"},{"key":"30_CR9","unstructured":"Goldberg, A.V., Hartline, J.D., et al.: Competitive auctions and digital goods. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201901, pp. 735\u2013744 (2001). ISBN: 0-89871-490-7"},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Gu, A., Gupta, A., et al.: The power of deferral: maintaining a constant-competitive Steiner tree online. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pp. 525\u2013534. ACM (2013)","DOI":"10.1145\/2488608.2488674"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., et al.: Maintaining assignments online: matching, scheduling, and flows. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 468\u2013479 (2014)","DOI":"10.1137\/1.9781611973402.35"},{"key":"30_CR12","doi-asserted-by":"crossref","unstructured":"Hartline, J.D., Roughgarden, T.: Simple versus optimal mechanisms. In: ACM Conference on Electronic Commerce, pp. 225\u2013234 (2009)","DOI":"10.1145\/1566374.1566407"},{"key":"30_CR13","unstructured":"Idury, R., Schaffer, A.: A better lower bound for on-line bottleneck matching (manuscript, 1992)"},{"issue":"3","key":"30_CR14","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1006\/jagm.1993.1026","volume":"14","author":"B Kalyanasundaram","year":"1993","unstructured":"Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"issue":"3","key":"30_CR15","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1137\/S0895480198342310","volume":"13","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: The online transportation problem. SIAM J. Discrete Math. 13(3), 370\u2013383 (2000)","journal-title":"SIAM J. Discrete Math."},{"key":"30_CR16","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47, 617\u2013643 (2000). ISSN: 0004\u20135411","journal-title":"J. ACM"},{"issue":"1","key":"30_CR17","doi-asserted-by":"publisher","first-page":"319","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. Theor. Comput. Sci. 233(1), 319\u2013325 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0304-3975(94)90042-6","volume":"127","author":"S Khuller","year":"1994","unstructured":"Khuller, S., Mitchell, S.G., et al.: On-line algorithms for weighted bipartite matching and stable marriages. Theor. Comput. Sci. 127, 255\u2013267 (1994). ISSN: 0304\u20133975","journal-title":"Theor. Comput. Sci."},{"key":"30_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/978-3-642-31594-7_58","volume-title":"Automata, Languages, and Programming","author":"N Megow","year":"2012","unstructured":"Megow, N., Skutella, M., Verschae, J., Wiese, A.: The power of recourse for online MST and TSP. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 689\u2013700. Springer, Heidelberg (2012)"},{"key":"30_CR20","doi-asserted-by":"crossref","unstructured":"Mehta, A., Saberi, A., et al.: Adwords and generalized online matching. J. ACM 54(5) (2007). ISSN: 0004\u20135411","DOI":"10.1145\/1284320.1284321"},{"issue":"2","key":"30_CR21","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00453-001-0068-9","volume":"32","author":"CA Phillips","year":"2002","unstructured":"Phillips, C.A., Stein, C., et al.: Optimal time-critical scheduling via resource augmentation. Algorithmica 32(2), 163\u2013200 (2002)","journal-title":"Algorithmica"},{"issue":"2","key":"30_CR22","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T Roughgarden","year":"2002","unstructured":"Roughgarden, T., Tardos, \u00c9.: How bad is selfish routing? J. ACM 49(2), 236\u2013259 (2002)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T14:49:31Z","timestamp":1559054971000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}