{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:43:52Z","timestamp":1787510632377,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642315848","type":"print"},{"value":"9783642315855","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31585-5_56","type":"book-chapter","created":{"date-parts":[[2012,6,23]],"date-time":"2012-06-23T07:56:29Z","timestamp":1340438189000},"page":"636-647","source":"Crossref","is-referenced-by-count":25,"title":["Online Mechanism Design (Randomized Rounding on the Fly)"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Krysta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"56_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Meyerson, A.: Reducing truth-telling online mechanisms to online optimization. In: STOC, pp. 503\u2013510 (2003)","DOI":"10.1145\/780615.780616"},{"key":"56_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Plotkin, S.A.: Throughput-competitive on-line routing. In: FOCS, pp. 32\u201340 (1993)","DOI":"10.1109\/SFCS.1993.366884"},{"key":"56_CR3","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: SODA, pp. 434\u2013443 (2007)"},{"key":"56_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-13036-6_28","volume-title":"Integer Programming and Combinatorial Optimization","author":"N. Bansal","year":"2010","unstructured":"Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: On k-Column Sparse Packing Programs. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 369\u2013382. Springer, Heidelberg (2010)"},{"key":"56_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Gonen, R., Nisan, N.: Incentive compatible multi unit combinatorial auctions. In: The Proc. of the 9th TARK, pp. 72\u201387 (2003)","DOI":"10.1145\/846247.846250"},{"key":"56_CR6","doi-asserted-by":"crossref","unstructured":"Blumrosen, L., Nisan, N.: Combinatorial auctions. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory (2007)","DOI":"10.1017\/CBO9780511800481.013"},{"key":"56_CR7","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press (1998)"},{"key":"56_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/11561071_61","volume-title":"Algorithms \u2013 ESA 2005","author":"N. Buchbinder","year":"2005","unstructured":"Buchbinder, N., Naor, J.: Online Primal-Dual Algorithms for Covering and Packing Problems. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 689\u2013701. Springer, Heidelberg (2005)"},{"key":"56_CR9","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J.: Improved bounds for online routing and packing via a primal-dual approach. In: FOCS, pp. 293\u2013304 (2006)","DOI":"10.1109\/FOCS.2006.39"},{"key":"56_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-540-74208-1_7","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S. Dobzinski","year":"2007","unstructured":"Dobzinski, S.: Two Randomized Mechanisms for Combinatorial Auctions. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 89\u2013103. Springer, Heidelberg (2007)"},{"key":"56_CR11","unstructured":"Dobzinski, S., Fu, H., Kleinberg, R.: Truthfulness via proxies. CoRR, abs\/1011.3232 (2010)"},{"key":"56_CR12","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Truthful randomized mechanisms for combinatorial auctions. In: STOC, pp. 644\u2013652 (2006)","DOI":"10.1145\/1132516.1132607"},{"key":"56_CR13","unstructured":"Dynkin, E.B.: The optimum choice of the instant for stopping a markov process. Sov. Math Dokl. 4 (1963)"},{"key":"56_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U.: On maximizing welfare when utility functions are subadditive. In: STOC, pp. 41\u201350 (2006)","DOI":"10.1145\/1132516.1132523"},{"issue":"1","key":"56_CR15","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/070680977","volume":"39","author":"U. Feige","year":"2009","unstructured":"Feige, U.: On maximizing welfare when utility functions are subadditive. SIAM J. Comput.\u00a039(1), 122\u2013142 (2009)","journal-title":"SIAM J. Comput."},{"key":"56_CR16","unstructured":"Kleinberg, R.D.: A multiple-choice secretary algorithm with applications to online auctions. In: SODA, pp. 630\u2013631 (2005)"},{"key":"56_CR17","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":"56_CR18","doi-asserted-by":"crossref","unstructured":"Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. In: Proc. of FOCS, pp. 595\u2013604 (2005)","DOI":"10.1109\/SFCS.2005.76"},{"key":"56_CR19","doi-asserted-by":"crossref","unstructured":"Lehmann, B., Lehmann, D.J., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. In: ACM Conference on Electronic Commerce, pp. 18\u201328 (2001)","DOI":"10.1145\/501158.501161"},{"key":"56_CR20","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Introduction to mechanism design (for computer scientists). In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory (2007)","DOI":"10.1017\/CBO9780511800481"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31585-5_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T09:50:12Z","timestamp":1743587412000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31585-5_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315848","9783642315855"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31585-5_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}