{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:02:38Z","timestamp":1725897758280},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642315930"},{"type":"electronic","value":"9783642315947"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_13","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"145-156","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints"],"prefix":"10.1007","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"13_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"A.A. Ageev","year":"2004","unstructured":"Ageev, A.A., Sviridenko, M.: Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim.\u00a08(3), 307\u2013328 (2004)","journal-title":"J. Comb. Optim."},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Fiat, A., Leighton, T.: Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract). In: STOC 1996: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 519\u2013530 (1996)","DOI":"10.1145\/237814.238000"},{"key":"13_CR3","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 434\u2013443 (2007)"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-642-15369-3_4","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","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":"13_CR5","unstructured":"Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press (1998)"},{"issue":"2-3","key":"13_CR6","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science\u00a03(2-3), 93\u2013263 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"13_CR7","unstructured":"Buchbinder, N., Naor, J. (Seffi)., Ravi, R., Singh, M.: Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints (2012), \n                    \n                      http:\/\/arxiv.org\/abs\/1205.1477"},{"key":"13_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-72792-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"G. Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract). In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 182\u2013196. Springer, Heidelberg (2007)"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Chawla, S., Hartline, J.D., Malec, D.L., Sivan, B.: Multi-parameter mechanism design and sequential posted pricing. In: ACM Symposium on Theory of Computing, pp. 311\u2013320 (2010)","DOI":"10.1145\/1807406.1807428"},{"issue":"8","key":"13_CR10","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G. Cornuejols","year":"1977","unstructured":"Cornuejols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Science\u00a023(8), 789\u2013810 (1977)","journal-title":"Management Science"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Dughmi, S., Roughgarden, T., Yan, Q.: From convex optimization to randomized mechanisms: toward optimal combinatorial auctions. In: ACM Symposium on Theory of Computing, pp. 149\u2013158 (2011)","DOI":"10.1145\/1993636.1993657"},{"key":"13_CR12","first-page":"69","volume-title":"Proceedings of the Calgary International Conference on Combinatorial Structures and their Application","author":"J. Edmonds","year":"1969","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Proceedings of the Calgary International Conference on Combinatorial Structures and their Application, pp. 69\u201387. Gordon and Breach, New York (1969)"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"M.L. Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions - part ii. Mathematical Programming\u00a014, 265\u2013294 (1978)","journal-title":"Mathematical Programming"},{"key":"13_CR14","unstructured":"Goundan, P.R., Schulz, A.S.: Revisiting the greedy approach to submodular set function maximization (January 2009) (preprint)"},{"key":"13_CR15","first-page":"99","volume":"82","author":"D.R. Karger","year":"1998","unstructured":"Karger, D.R.: Random sampling and greedy sparsification for matroid optimization problems. Mathematical Programming\u00a082, 99\u2013116 (1998)","journal-title":"Mathematical Programming"},{"issue":"1","key":"13_CR16","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-007-9105-7","volume":"52","author":"S. Khot","year":"2008","unstructured":"Khot, S., Lipton, R.J., Markakis, E., Mehta, A.: Inapproximability results for combinatorial auctions with submodular utility functions. Algorithmica\u00a052(1), 3\u201318 (2008)","journal-title":"Algorithmica"},{"key":"13_CR17","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":"13_CR18","doi-asserted-by":"crossref","unstructured":"Mirrokni, V.S., Schapira, M., Vondr\u00e1k, J.: Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In: ACM Conference on Electronic Commerce, pp. 70\u201377 (2008)","DOI":"10.1145\/1386790.1386805"},{"issue":"3","key":"13_CR19","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best Algorithms for Approximating the Maximum of a Submodular Set Function. Mathematics of Operations Research\u00a03(3), 177\u2013188 (1978)","journal-title":"Mathematics of Operations Research"},{"key":"13_CR20","unstructured":"Schrijver, A.: Combinatorial optimization - polyhedra and efficiency. Springer (2005)"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Vondrak, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: STOC 2008: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"}],"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_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:14:49Z","timestamp":1620130489000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}