{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T19:11:01Z","timestamp":1751483461929,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2018,12,11]],"date-time":"2018-12-11T00:00:00Z","timestamp":1544486400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00453-018-00532-x","type":"journal-article","created":{"date-parts":[[2018,12,11]],"date-time":"2018-12-11T04:46:39Z","timestamp":1544503599000},"page":"2244-2269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Optimization with Demand Oracles"],"prefix":"10.1007","volume":"81","author":[{"given":"Ashwinkumar","family":"Badanidiyuru","sequence":"first","affiliation":[]},{"given":"Shahar","family":"Dobzinski","sequence":"additional","affiliation":[]},{"given":"Sigal","family":"Oren","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,12,11]]},"reference":[{"key":"532_CR1","doi-asserted-by":"crossref","unstructured":"Anari, N., Goel, G., Nikzad, A.: Mechanism design for crowdsourcing: an optimal 1-1\/e competitive budget-feasible mechanism for large markets. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 266\u2013275. IEEE (2014)","DOI":"10.1109\/FOCS.2014.36"},{"key":"532_CR2","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Dobzinski, S., Fu, H., Kleinberg, R., Nisan, N., Roughgarden, T.: Sketching valuation functions. In: SODA, pp. 1025\u20131035 (2012)","DOI":"10.1137\/1.9781611973099.81"},{"key":"532_CR3","doi-asserted-by":"crossref","unstructured":"Balcan, M.F., Blum, A., Mansour, Y.: Item pricing for revenue maximization. In: EC (2008)","DOI":"10.1145\/1386790.1386802"},{"key":"532_CR4","doi-asserted-by":"crossref","unstructured":"Bei, X., Chen, N., Gravin, N., Lu, P.: Budget feasible mechanism design: from prior-free to Bayesian. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 449\u2013458. ACM (2012)","DOI":"10.1145\/2213977.2214020"},{"key":"532_CR5","volume-title":"Algorithmic Game Theory","author":"L Blumrosen","year":"2007","unstructured":"Blumrosen, L., Nisan, N.: Combinatorial auctions (a survey). In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)"},{"issue":"4","key":"532_CR6","doi-asserted-by":"publisher","first-page":"1372","DOI":"10.1137\/050641181","volume":"39","author":"L Blumrosen","year":"2009","unstructured":"Blumrosen, L., Nisan, N.: On the computational power of demand queries. SIAM J. Comput. 39(4), 1372\u20131391 (2009)","journal-title":"SIAM J. Comput."},{"key":"532_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: STOC (2011)","DOI":"10.1145\/1993636.1993740"},{"issue":"3","key":"532_CR8","first-page":"30","volume":"13","author":"K Cohavi","year":"2017","unstructured":"Cohavi, K., Dobzinski, S.: Faster and simpler sketches of valuation functions. ACM Trans. Algorithms (TALG) 13(3), 30 (2017)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"532_CR9","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Fu, H., Kleinberg, R.: On the complexity of computing an equilibrium in combinatorial auctions. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 110\u2013122. SIAM (2014)","DOI":"10.1137\/1.9781611973730.9"},{"key":"532_CR10","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Approximation algorithms for combinatorial auctions with complement-free bidders. In: STOC (2005)","DOI":"10.1145\/1060590.1060681"},{"key":"532_CR11","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Nisan, N., Schapira, M.: Truthful randomized mechanisms for combinatorial auctions. In: STOC (2006)","DOI":"10.1145\/1132516.1132607"},{"key":"532_CR12","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Papadimitriou, C., Singer, Y.: Mechanisms for complement-free procurement. In: EC (2011)","DOI":"10.1145\/1993574.1993615"},{"issue":"4","key":"532_CR13","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"532_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U.: On maximizing welfare where the utility functions are subadditive. In: STOC (2006)","DOI":"10.1145\/1132516.1132523"},{"key":"532_CR15","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondr\u00e1k, J.: Approximation algorithms for allocation problems: improving the factor of 1-1\/e. In: FOCS (2006)","DOI":"10.1109\/FOCS.2006.14"},{"key":"532_CR16","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume-title":"Polyhedral Combinatorics. Volume 8 of Mathematical Programming Studies","author":"ML Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions: II. Polyhedral Combinatorics. Volume 8 of Mathematical Programming Studies, pp. 73\u201387. Springer, Berlin (1978)"},{"key":"532_CR17","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Vondr\u00e1k, J.: Submodular maximization by simulated annealing. In: SODA (2011)","DOI":"10.1137\/1.9781611973082.83"},{"issue":"1","key":"532_CR18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"key":"532_CR19","doi-asserted-by":"crossref","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: SODA (2009)","DOI":"10.1137\/1.9781611973068.60"},{"key":"532_CR20","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Approximations for monotone and non-monotone submodular maximization with knapsack constraints. CoRR. \n                    arXiv:1101.2940\n                    \n                   [cs.DS] (2011)"},{"key":"532_CR21","unstructured":"Lahaie, S., Constantin, F., Parkes, D.C.: More on the power of demand queries in combinatorial auctions: learning atomic languages and handling incentives. In: IJCAI (2005)"},{"key":"532_CR22","unstructured":"Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. In: FOCS (2005)"},{"key":"532_CR23","doi-asserted-by":"crossref","unstructured":"Lee, J., Mirrokni, V.S.., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under matroid and knapsack constraints. In: STOC (2009)","DOI":"10.1145\/1536414.1536459"},{"key":"532_CR24","doi-asserted-by":"crossref","unstructured":"Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. In: EC (2001)","DOI":"10.1145\/501158.501161"},{"issue":"3","key":"532_CR25","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177\u2013188 (1978)","journal-title":"Math. Oper. Res."},{"key":"532_CR26","unstructured":"Nisan, N., Segal, I.: Exponential communication inefficiency of demand queries. In: TARK (2005)"},{"key":"532_CR27","volume-title":"Combinatorial Auctions Cramton","author":"T Sandholm","year":"2006","unstructured":"Sandholm, T., Boutilier, C.: Preference elicitation in combinatorial auctions. In: Cramton, P., Shoham, Y., Steinberg, R. (eds.) Combinatorial Auctions Cramton. MIT Press, Boston (2006)"},{"key":"532_CR28","doi-asserted-by":"crossref","unstructured":"Singer, Y.: Budget feasible mechanisms. In: FOCS (2010)","DOI":"10.1109\/FOCS.2010.78"},{"issue":"1","key":"532_CR29","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"532_CR30","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: STOC (2008)","DOI":"10.1145\/1374376.1374389"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00532-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-00532-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00532-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,10]],"date-time":"2019-12-10T19:20:19Z","timestamp":1576005619000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-00532-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,11]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["532"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-00532-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,12,11]]},"assertion":[{"value":"29 June 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}