{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T05:14:07Z","timestamp":1784178847339,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642404498","type":"print"},{"value":"9783642404504","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_50","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"589-600","source":"Crossref","is-referenced-by-count":60,"title":["An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Kesselheim","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Klaus","family":"Radke","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"T\u00f6nnis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"50_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: SODA, pp. 1253\u20131264 (2011)","DOI":"10.1137\/1.9781611973082.95"},{"issue":"1","key":"50_CR2","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s00453-005-1172-z","volume":"44","author":"Y. Azar","year":"2006","unstructured":"Azar, Y., Regev, O.: Combinatorial algorithms for the unsplittable flow problem. Algorithmica\u00a044(1), 49\u201366 (2006)","journal-title":"Algorithmica"},{"key":"50_CR3","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.D.: Matroids, secretary problems, and online mechanisms. In: SODA, pp. 434\u2013443 (2007)"},{"issue":"1","key":"50_CR4","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1145\/1360443.1360462","volume":"39","author":"B.E. Birnbaum","year":"2008","unstructured":"Birnbaum, B.E., Mathieu, C.: On-line bipartite matching made simple. SIGACT News\u00a039(1), 80\u201387 (2008)","journal-title":"SIGACT News"},{"key":"50_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-642-13036-6_13","volume-title":"Integer Programming and Combinatorial Optimization","author":"N. Buchbinder","year":"2010","unstructured":"Buchbinder, N., Jain, K., Singh, M.: Secretary problems via linear programming. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 163\u2013176. Springer, Heidelberg (2010)"},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Lachish, O.: Improved competitive ratio for the matroid secretary problem. In: SODA, pp. 1702\u20131712 (2012)","DOI":"10.1137\/1.9781611973099.135"},{"key":"50_CR7","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: ACM Conference on Electronic Commerce, pp. 71\u201378 (2009)","DOI":"10.1145\/1566374.1566384"},{"key":"50_CR8","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of ranking for online bipartite matching. In: SODA, pp. 101\u2013107 (2013)","DOI":"10.1137\/1.9781611973105.7"},{"issue":"1-2","key":"50_CR9","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s00453-010-9457-2","volume":"62","author":"N.B. Dimitrov","year":"2012","unstructured":"Dimitrov, N.B., Plaxton, C.G.: Competitive weighted matching in transversal matroids. Algorithmica\u00a062(1-2), 333\u2013348 (2012)","journal-title":"Algorithmica"},{"key":"50_CR10","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J., Schwartz, R.: Improved competitive ratios for submodular secretary problems (extended abstract). In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) RANDOM\/APPROX 2011. LNCS, vol.\u00a06845, pp. 218\u2013229. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-22935-0_19"},{"key":"50_CR11","doi-asserted-by":"crossref","unstructured":"Ferguson, T.S.: Who solved the secretary problem? Statistical Science, 282\u2013289 (1989)","DOI":"10.1214\/ss\/1177012493"},{"key":"50_CR12","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: SODA, pp. 982\u2013991 (2008)"},{"key":"50_CR13","doi-asserted-by":"crossref","unstructured":"Im, S., Wang, Y.: Secretary problems: Laminar matroid and interval scheduling. In: SODA, pp. 1265\u20131274 (2011)","DOI":"10.1137\/1.9781611973082.96"},{"key":"50_CR14","doi-asserted-by":"crossref","unstructured":"Jaillet, P., Soto, J.A., Zenklusen, R.: Advances on matroid secretary problems: Free order model and laminar case. CoRR abs\/1207.1333 (2012)","DOI":"10.1007\/978-3-642-36694-9_22"},{"issue":"3","key":"50_CR15","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\u00a014(3), 478\u2013488 (1993)","journal-title":"J. Algorithms"},{"key":"50_CR16","doi-asserted-by":"crossref","unstructured":"Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: STOC, pp. 587\u2013596 (2011)","DOI":"10.1145\/1993636.1993715"},{"key":"50_CR17","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: STOC, pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"key":"50_CR18","unstructured":"Kleinberg, R.D.: A multiple-choice secretary algorithm with applications to online auctions. In: SODA, pp. 630\u2013631 (2005)"},{"key":"50_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/978-3-642-02930-1_42","volume-title":"Automata, Languages and Programming","author":"N. Korula","year":"2009","unstructured":"Korula, N., P\u00e1l, M.: Algorithms for secretary problems on graphs and hypergraphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol.\u00a05556, pp. 508\u2013520. Springer, Heidelberg (2009)"},{"key":"50_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1007\/978-3-642-31585-5_56","volume-title":"Automata, Languages, and Programming","author":"P. Krysta","year":"2012","unstructured":"Krysta, P., V\u00f6cking, B.: Online mechanism design (randomized rounding on the fly). In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol.\u00a07392, pp. 636\u2013647. Springer, Heidelberg (2012)"},{"key":"50_CR21","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In: STOC, pp. 597\u2013606 (2011)","DOI":"10.1145\/1993636.1993716"},{"key":"50_CR22","doi-asserted-by":"crossref","unstructured":"Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized online matching. J. ACM\u00a054(5) (2007)","DOI":"10.1145\/1284320.1284321"},{"key":"50_CR23","doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic game theory. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511800481"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_50","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T12:54:04Z","timestamp":1558011244000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}