{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T07:07:07Z","timestamp":1774940827449,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642315930","type":"print"},{"value":"9783642315947","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_59","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"701-713","source":"Crossref","is-referenced-by-count":9,"title":["Geometry of Online Packing Linear Programs"],"prefix":"10.1007","author":[{"given":"Marco","family":"Molinaro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"59_CR1","unstructured":"Agrawal, S., Wang, Z., Ye, Y.: A dynamic near-optimal algorithm for online linear programming, \n                    \n                      http:\/\/arxiv.org\/abs\/0911.2974"},{"key":"59_CR2","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Dinitz, M., Gupta, A., Immorlica, N., Talwar, K.: Secretary problems: weights and discounts. In: SODA (2009)","DOI":"10.1137\/1.9781611973068.135"},{"key":"59_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-540-74208-1_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Babaioff","year":"2007","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.D.: A Knapsack Secretary Problem with Applications. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 16\u201328. Springer, Heidelberg (2007)"},{"key":"59_CR4","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Online auctions and generalized secretary problems. SIGecom Exchanges\u00a07(2) (2008)","DOI":"10.1145\/1399589.1399596"},{"key":"59_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/978-3-642-15369-3_4","volume-title":"APPROX and RANDOM 2010","author":"M. Bateni","year":"2010","unstructured":"Bateni, M., Hajiaghayi, M., Zadimoghaddam, M.: Submodular Secretary Problem and Extensions. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010, LNCS, vol.\u00a06302, pp. 39\u201352. Springer, Heidelberg (2010)"},{"key":"59_CR6","unstructured":"Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer Series in Operations Research and Financial Engineering. Springer (1997)"},{"key":"59_CR7","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press (1998)"},{"key":"59_CR8","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.S.: Online primal-dual algorithms for covering and packing. Mathematics of Operations Research\u00a034, 270\u2013286 (2009)","journal-title":"Mathematics of Operations Research"},{"key":"59_CR9","doi-asserted-by":"crossref","unstructured":"Cucker, F., Zhou, D.X.: Learning Theory: An Approximation Theory Viewpoint. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511618796"},{"key":"59_CR10","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Sivan, B., Wilkens, C.A.: Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In: EC (2011)","DOI":"10.1145\/1993574.1993581"},{"key":"59_CR11","doi-asserted-by":"crossref","unstructured":"Devenur, N.R., Hayes, T.P.: The adwords problem: online keyword matching with budgeted bidders under random permutations. In: EC (2009)","DOI":"10.1145\/1566374.1566384"},{"key":"59_CR12","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1109\/TIT.1979.1056087","volume":"25","author":"L. Devroye","year":"1979","unstructured":"Devroye, L., Wagner, T.: Distribution-free performance bounds for potential function rules. IEEE Transactions on Information Theory\u00a025, 601\u2013604 (1979)","journal-title":"IEEE Transactions on Information Theory"},{"key":"59_CR13","unstructured":"Dynkin, E.B.: The optimum choice of the instant for stopping a Markov process. Soviet Mathematics Doklady\u00a04 (1963)"},{"key":"59_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-15775-2_16","volume-title":"Algorithms \u2013 ESA 2010","author":"J. Feldman","year":"2010","unstructured":"Feldman, J., Henzinger, M., Korula, N., Mirrokni, V.S., Stein, C.: Online Stochastic Packing Applied to Display Ad Allocation. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol.\u00a06346, pp. 182\u2013194. Springer, Heidelberg (2010)"},{"issue":"313","key":"59_CR15","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1080\/01621459.1966.10502008","volume":"61","author":"J.P. Gilbert","year":"1966","unstructured":"Gilbert, J.P., Mosteller, F.: Recognizing the Maximum of a Sequence. Journal of the American Statistical Association\u00a061(313), 35\u201373 (1966)","journal-title":"Journal of the American Statistical Association"},{"key":"59_CR16","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: SODA (2008)"},{"key":"59_CR17","doi-asserted-by":"crossref","unstructured":"Im, S., Wang, Y.: Secretary problems: Laminar matroid and interval scheduling. In: SODA (2011)","DOI":"10.1137\/1.9781611973082.96"},{"key":"59_CR18","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: STOC (1990)","DOI":"10.1145\/100216.100262"},{"key":"59_CR19","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. In: SODA (1996)"},{"key":"59_CR20","unstructured":"Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: SODA (2005)"},{"key":"59_CR21","unstructured":"Kutin, S., Niyogi, P.: Almost-everywhere algorithmic stability and generalization error. In: Uncertainty in Artificial Intelligence, pp. 275\u2013282 (2002)"},{"key":"59_CR22","unstructured":"Molinaro, M., Ravi, R.: Geometry of online packing linear programs, \n                    \n                      http:\/\/arxiv.org\/abs\/1204.5810"},{"key":"59_CR23","doi-asserted-by":"crossref","unstructured":"Soto, J.A.: Matroid secretary problem in the random assignment model. In: SODA (2011)","DOI":"10.1137\/1.9781611973082.97"}],"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-31594-7_59.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:15:11Z","timestamp":1620130511000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_59","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}